{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T15:41:36Z","timestamp":1787499696785,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540228493","type":"print"},{"value":"9783540278368","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27836-8_48","type":"book-chapter","created":{"date-parts":[[2010,9,15]],"date-time":"2010-09-15T18:53:21Z","timestamp":1284576801000},"page":"555-567","source":"Crossref","is-referenced-by-count":12,"title":["Bounded Fixed-Parameter Tractability and log2 n Nondeterministic Bits"],"prefix":"10.1007","author":[{"given":"J\u00f6rg","family":"Flum","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Grohe","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mark","family":"Weyer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"48_CR1","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0168-0072(94)00034-Z","volume":"73","author":"K.A. Abrahamson","year":"1995","unstructured":"Abrahamson, K.A., Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogs. Annals of pure and applied logic\u00a073, 235\u2013276 (1995)","journal-title":"Annals of pure and applied logic"},{"key":"48_CR2","first-page":"194","volume-title":"Handbook of Theoretical Computer Science","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: Graph rewriting: An algebraic and logic approach. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, vol.\u00a0B, pp. 194\u2013242. Elsevier Science Publishers, Amsterdam (1990)"},{"key":"48_CR3","doi-asserted-by":"crossref","unstructured":"Downey, R.: Parameterized complexity for the skeptic. In: Proceedings of the 18th IEEE Conference on Computational Complexity (2003)","DOI":"10.1109\/CCC.2003.1214417"},{"key":"48_CR4","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Evans, P.A., Fellows, M.R.: Parameterized learning complexity. In: Proceedings of the 6th Annual ACM Conference on Computational Learning Theory, pp. 51\u201357 (1993)","DOI":"10.1145\/168304.168311"},{"key":"48_CR5","first-page":"166","volume-title":"Complexity Theory","author":"R.G. Downey","year":"1993","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness III: Some structural aspects of the W-hierarchy. In: Ambos-Spies, K., Homer, S., Sch\u00f6ning, U. (eds.) Complexity Theory, pp. 166\u2013191. Cambridge University Press, Cambridge (1993)"},{"key":"48_CR6","doi-asserted-by":"crossref","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. Springer, Heidelberg (1999)"},{"key":"48_CR7","series-title":"AMS-DIMACS Volume Series","first-page":"119","volume-title":"Proof Complexity and Feasible Arithmetic","author":"R.G. Downey","year":"1998","unstructured":"Downey, R.G., Fellows, M.R., Regan, K.: Descriptive complexity and the W-hierarchy. In: Beame, P., Buss, S. (eds.) Proof Complexity and Feasible Arithmetic. AMS-DIMACS Volume Series, vol.\u00a039, pp. 119\u2013134. AMS, Providence (1998)"},{"key":"48_CR8","doi-asserted-by":"crossref","unstructured":"Eiter, T., Gottlob, G., Makino, K.: New results on monotone dualization and generating hypergraph transversals. In: Proceedings of the 34th ACMSymposium on Theory of Computing, pp. 14\u201322 (2002)","DOI":"10.1145\/509907.509912"},{"issue":"1","key":"48_CR9","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1137\/S0097539799360768","volume":"31","author":"J. Flum","year":"2001","unstructured":"Flum, J., Grohe, M.: Fixed-parameter tractability, definability, and model checking. SIAM Journal on Computing\u00a031(1), 113\u2013145 (2001)","journal-title":"SIAM Journal on Computing"},{"key":"#cr-split#-48_CR10.1","doi-asserted-by":"crossref","unstructured":"Flum, J., Grohe, M.: Model-checking problems as a basis for parameterized intractability. To appear in Proceedings of the 19th IEEE Symposium on Logic in Computer Science (2004);","DOI":"10.1109\/LICS.2004.1319633"},{"key":"#cr-split#-48_CR10.2","unstructured":"Full version available as Technical Report 23\/2003, Fakult\u00e4t f\u00fcr Mathematik und Physik, Albert-Ludwigs-Universit\u00e4t Freiburg (2003)"},{"key":"48_CR11","doi-asserted-by":"crossref","unstructured":"Flum, J., Grohe, M., Weyer, M.: Bounded fixed-parameter tractability and log2n nondeterministic bits. Technical Report 04\/2004, Fakult\u00e4t f\u00fcr Mathematik und Physik, Albert- Ludwigs-Universit\u00e4t Freiburg (2004)","DOI":"10.1007\/978-3-540-27836-8_48"},{"key":"48_CR12","doi-asserted-by":"crossref","unstructured":"Frick, M., Grohe, M.: The complexity of first-order and monadic second-order logic revisited. In: Proceedings of the 17th IEEE Symposium on Logic in Computer Science, pp. 215\u2013224 (2002)","DOI":"10.1109\/LICS.2002.1029830"},{"issue":"4","key":"48_CR13","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1145\/637411.637428","volume":"31","author":"M. Grohe","year":"2002","unstructured":"Grohe, M.: Parameterized complexity for the database theorist. SIGMOD Record\u00a031(4), 86\u201396 (2002)","journal-title":"SIGMOD Record"},{"key":"48_CR14","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1137\/0209003","volume":"9","author":"C. Kintala","year":"1980","unstructured":"Kintala, C., Fischer, P.: Refining nondeterminism in relativised polynomial time bounded computations. SIAM Journal on Computing\u00a09, 46\u201353 (1980)","journal-title":"SIAM Journal on Computing"},{"key":"48_CR15","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1006\/jcss.1996.0058","volume":"53","author":"C.H. Papadimitriou","year":"1996","unstructured":"Papadimitriou, C.H., Yannakakis, M.: On limited nondeterminism and the complexity of V-C dimension. Journal of Computer and System Sciences\u00a053, 161\u2013170 (1996)","journal-title":"Journal of Computer and System Sciences"},{"key":"48_CR16","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1006\/jcss.1998.1602","volume":"58","author":"M. Schaefer","year":"1999","unstructured":"Schaefer, M.: Deciding the Vapnik-C\u011brvonenkis dimension is $\\Sigma^P_3$ -complete. Journal of Computer and System Sciences\u00a058, 177\u2013182 (1999)","journal-title":"Journal of Computer and System Sciences"},{"key":"48_CR17","unstructured":"Weyer, M.: PhD thesis (in preparation)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27836-8_48.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T23:23:58Z","timestamp":1605741838000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27836-8_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228493","9783540278368"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27836-8_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}