{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:34:42Z","timestamp":1759638882179},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662460771"},{"type":"electronic","value":"9783662460788"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-46078-8_18","type":"book-chapter","created":{"date-parts":[[2015,1,14]],"date-time":"2015-01-14T14:54:29Z","timestamp":1421247269000},"page":"217-229","source":"Crossref","is-referenced-by-count":1,"title":["Machine Characterizations for Parameterized Complexity Classes Beyond Para-NP"],"prefix":"10.1007","author":[{"given":"Ronald","family":"de Haan","sequence":"first","affiliation":[]},{"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"18_CR1","doi-asserted-by":"publisher","first-page":"660","DOI":"10.1006\/jcss.1999.1691","volume":"60","author":"M. Ajtai","year":"2000","unstructured":"Ajtai, M., Fagin, R., Stockmeyer, L.J.: The closure of monadic NP. J. of Computer and System Sciences\u00a060(3), 660\u2013716 (2000)","journal-title":"J. of Computer and System Sciences"},{"doi-asserted-by":"crossref","unstructured":"Arora, S., Barak, B.: Computational Complexity \u2013 A Modern Approach. Cambridge University Press (2009)","key":"18_CR2","DOI":"10.1017\/CBO9780511804090"},{"unstructured":"Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.): Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications, vol.\u00a0185. IOS Press (2009)","key":"18_CR3"},{"key":"18_CR4","doi-asserted-by":"publisher","first-page":"654","DOI":"10.1016\/S0022-0000(03)00073-4","volume":"67","author":"M. Cesati","year":"2003","unstructured":"Cesati, M.: The Turing way to parameterized complexity. J. of Computer and System Sciences\u00a067, 654\u2013685 (2003)","journal-title":"J. of Computer and System Sciences"},{"key":"18_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1007\/978-3-642-30891-8_17","volume-title":"The Multivariate Algorithmic Revolution and Beyond","author":"Y. Chen","year":"2012","unstructured":"Chen, Y., Flum, J.: A parameterized halting problem. In: Bodlaender, H.L., Downey, R., Fomin, F.V., Marx, D. (eds.) Fellows Festschrift 2012. LNCS, vol.\u00a07370, pp. 364\u2013397. Springer, Heidelberg (2012)"},{"key":"18_CR6","series-title":"Monographs in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)"},{"doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer (2013)","key":"18_CR7","DOI":"10.1007\/978-1-4471-5559-1"},{"unstructured":"Endriss, U., de Haan, R., Szeider, S.: Parameterized complexity results for agenda safety in judgment aggregation. In: Proceedings of the 5th International Workshop on Computational Social Choice (COMSOC 2014). Carnegie Mellon University (2014)","key":"18_CR8"},{"doi-asserted-by":"crossref","unstructured":"Fichte, J.K., Szeider, S.: Backdoors to normality for disjunctive logic programs. In: Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence (AAAI 2013), pp. 320\u2013327. AAAI Press (2013)","key":"18_CR9","DOI":"10.1609\/aaai.v27i1.8624"},{"issue":"2","key":"18_CR10","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/S0890-5401(03)00161-5","volume":"187","author":"J. Flum","year":"2003","unstructured":"Flum, J., Grohe, M.: Describing parameterized complexity classes. Information and Computation\u00a0187(2), 291\u2013319 (2003)","journal-title":"Information and Computation"},{"key":"18_CR11","series-title":"An EATCS Series","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. An EATCS Series, vol.\u00a0XIV. Springer, Berlin (2006)"},{"doi-asserted-by":"crossref","unstructured":"Gomes, C.P., Kautz, H., Sabharwal, A., Selman, G.: Satisfiability solvers. In Handbook of Knowledge Representation. Foundations of Artificial Intelligence, vol.\u00a03, pp. 89\u2013134. Elsevier (2008)","key":"18_CR12","DOI":"10.1016\/S1574-6526(07)03002-7"},{"key":"18_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-3-319-09284-3_8","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2014","author":"R. Haan de","year":"2014","unstructured":"de Haan, R., Szeider, S.: Fixed-parameter tractable reductions to SAT. In: Sinz, C., Egly, U. (eds.) SAT 2014. LNCS, vol.\u00a08561, pp. 85\u2013102. Springer, Heidelberg (2014)"},{"unstructured":"De Haan, R., Szeider, S.: The parameterized complexity of reasoning problems beyond NP. In: Baral, C., De Giacomo, G., Eiter, T. (eds.) Principles of Knowledge Representation and Reasoning: Proceedings of the Fourteenth International Conference, KR 2014, Vienna, Austria, July 20-24. AAAI Press (2014)","key":"18_CR14"},{"unstructured":"De Haan, R., Szeider, S.: The parameterized complexity of reasoning problems beyond NP. Technical Report 1312.1672v3, arXiv.org (2014)","key":"18_CR15"},{"doi-asserted-by":"crossref","unstructured":"Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 2nd edn. Addison-Wesley Series in Computer Science. Addison-Wesley-Longman (2001)","key":"18_CR16","DOI":"10.1145\/568438.568455"},{"issue":"8","key":"18_CR17","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1145\/1536616.1536637","volume":"52","author":"S. Malik","year":"2009","unstructured":"Malik, S., Zhang, L.: Boolean satisfiability from theoretical hardness to practical success. Communications of the ACM\u00a052(8), 76\u201382 (2009)","journal-title":"Communications of the ACM"},{"doi-asserted-by":"crossref","unstructured":"Meyer, A.R., Stockmeyer, L.J.: The equivalence problem for regular expressions with squaring requires exponential space. In: SWAT, pp. 125\u2013129. IEEE Computer Soc. (1972)","key":"18_CR18","DOI":"10.1109\/SWAT.1972.29"},{"key":"18_CR19","series-title":"Oxford Lecture Series in Mathematics and its Applications","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford (2006)"},{"unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley (1994)","key":"18_CR20"},{"unstructured":"Pfandler, A., R\u00fcmmele, S., Szeider, S.: Backdoors to abduction. In: Rossi, F. (ed.) Proceedings of the 23rd International Joint Conference on Artificial Intelligence, IJCAI 2013. AAAI Press\/IJCAI (2013)","key":"18_CR21"},{"key":"18_CR22","first-page":"96","volume":"103","author":"K.A. Sakallah","year":"2011","unstructured":"Sakallah, K.A., Marques-Silva, J.: Anatomy and empirical evaluation of modern SAT solvers. Bulletin of the European Association for Theoretical Computer Science\u00a0103, 96\u2013121 (2011)","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"issue":"1","key":"18_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L.J. Stockmeyer","year":"1976","unstructured":"Stockmeyer, L.J.: The polynomial-time hierarchy. Theoretical Computer Science\u00a03(1), 1\u201322 (1976)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"18_CR24","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0304-3975(76)90062-1","volume":"3","author":"C. Wrathall","year":"1976","unstructured":"Wrathall, C.: Complete sets and the polynomial-time hierarchy. Theoretical Computer Science\u00a03(1), 23\u201333 (1976)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2015: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-46078-8_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,31]],"date-time":"2023-07-31T23:51:12Z","timestamp":1690847472000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-46078-8_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662460771","9783662460788"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-46078-8_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}