{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,7]],"date-time":"2026-06-07T08:48:18Z","timestamp":1780822098031,"version":"3.54.1"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2014,10,16]],"date-time":"2014-10-16T00:00:00Z","timestamp":1413417600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,3]]},"DOI":"10.1007\/s00453-014-9944-y","type":"journal-article","created":{"date-parts":[[2014,10,15]],"date-time":"2014-10-15T15:04:33Z","timestamp":1413385473000},"page":"661-701","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":34,"title":["On the Space and Circuit Complexity of Parameterized Problems: Classes and Completeness"],"prefix":"10.1007","volume":"71","author":[{"given":"Michael","family":"Elberfeld","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christoph","family":"Stockhusen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Till","family":"Tantau","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2014,10,16]]},"reference":[{"issue":"1","key":"9944_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/jagm.1993.1001","volume":"14","author":"HL Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: On linear time minor tests with depth-first search. J. Algorithms 14(1), 1\u201323 (1993). doi: 10.1006\/jagm.1993.1001","journal-title":"J. Algorithms"},{"key":"9944_CR2","unstructured":"Buss, J., Goldsmith, J.: Nondeterminism within P*. SIAM J. Comput. 22, 560\u2013572 (1993)"},{"issue":"4","key":"9944_CR3","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1137\/0221046","volume":"21","author":"S Buss","year":"1992","unstructured":"Buss, S., Cook, S., Gupta, A., Ramachandran, V.: An optimal parallel algorithm for formula evaluation. SIAM J. Comput. 21(4), 755\u2013780 (1992). doi: 10.1137\/0221046","journal-title":"SIAM J. Comput."},{"key":"9944_CR4","doi-asserted-by":"crossref","unstructured":"Buss, S.R.: The Boolean formula value problem is in alogtime. In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC 1987), ACM, pp. 123\u2013131. (1987). doi: 10.1145\/28395.28409","DOI":"10.1145\/28395.28409"},{"issue":"1","key":"9944_CR5","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/S0168-0072(95)00020-8","volume":"84","author":"L Cai","year":"1997","unstructured":"Cai, L., Chen, J., Downey, R.G., Fellows, M.R.: Advice classes of parameterized tractability. Ann. Pure Appl. Log. 84(1), 119\u2013138 (1997a). doi: 10.1016\/S0168-0072(95)00020-8","journal-title":"Ann. Pure Appl. Log."},{"issue":"4\u20135","key":"9944_CR6","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/s001530050069","volume":"36","author":"L Cai","year":"1997","unstructured":"Cai, L., Chen, J., Downey, R.G., Fellows, M.R.: On the parameterized complexity of short computation and factorization. Arch. Math. Log. 36(4\u20135), 321\u2013337 (1997b)","journal-title":"Arch. Math. Log."},{"key":"9944_CR7","doi-asserted-by":"crossref","unstructured":"Chen, H., M\u00fcller, M.: The fine classification of conjunctive queries and parameterized logarithmic space complexity. In: PODS \u201913 Proceedings of the 32nd Symposium on Principles of Database Systems, ACM, pp. 309\u2013320. (2013). doi: 10.1145\/2463664.2463669","DOI":"10.1145\/2463664.2463669"},{"issue":"5","key":"9944_CR8","doi-asserted-by":"crossref","first-page":"21:2","DOI":"10.1145\/1411509.1411511","volume":"55","author":"J Chen","year":"2008","unstructured":"Chen, J., Liu, Y., Lu, S., O\u2019Sullivan, B., Razgon, I.: A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM 55(5), 21:2\u201321:19 (2008). doi: 10.1145\/1411509.1411511","journal-title":"J. ACM"},{"key":"9944_CR9","doi-asserted-by":"crossref","unstructured":"Chen, Y., Flum, J., Grohe, M.: Bounded nondeterminism and alternation in parameterized complexity theory. In: Proceedings of the 18th IEEE Annual Conference on Computational Complexity (CCCC 2003), pp. 13\u201329. (2003). doi: 10.1109\/ccc.2003.1214407","DOI":"10.1109\/CCC.2003.1214407"},{"key":"9944_CR10","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)"},{"key":"9944_CR11","doi-asserted-by":"crossref","unstructured":"Elberfeld, M., Stockhusen, C., Tantau, T.: On the space complexity of parameterized problems. In: Thilikos, D.M., Woeginger, G.J. (eds.) Parameterized and Exact Computation, Lecture Notes in Computer Science, vol. 7535, pp. 206\u2013217. Springer, Berlin. (2012).doi: 10.1007\/978-3-642-33293-7_20","DOI":"10.1007\/978-3-642-33293-7_20"},{"issue":"1","key":"9944_CR12","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1016\/S0196-6774(03)00081-6","volume":"49","author":"M Fellows","year":"2003","unstructured":"Fellows, M., Hallett, M., Stege, U.: Analogs & duals of the mast problem for squences & trees. J. Algorithms 49(1), 192\u2013216 (2003)","journal-title":"J. Algorithms"},{"key":"9944_CR13","doi-asserted-by":"crossref","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. Inf. Comput. 187, 291\u2013319 (2003). doi: 10.1016\/S0890-5401(03)00161-5","journal-title":"Inf. Comput."},{"key":"9944_CR14","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006). doi: 10.1007\/3-540-29953-X"},{"issue":"1","key":"9944_CR15","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/j.disopt.2010.08.003","volume":"8","author":"S Guillemot","year":"2011","unstructured":"Guillemot, S.: Parameterized complexity and approximability of the longest compatible sequence problem. Discret. Optim. 8(1), 50\u201360 (2011). doi: 10.1016\/j.disopt.2010.08.003","journal-title":"Discret. Optim."},{"key":"9944_CR16","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1007\/BF00289513","volume":"1","author":"J Hartmanis","year":"1972","unstructured":"Hartmanis, J.: On non-determinancy in simple computing devices. Acta Inform. 1, 336\u2013344 (1972). doi: 10.1007\/BF00289513","journal-title":"Acta Inform."},{"issue":"3","key":"9944_CR17","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1137\/0211050","volume":"11","author":"JW Hong","year":"1982","unstructured":"Hong, J.W.: On some deterministic space complexity problems. SIAM J. Comput. 11(3), 591\u2013601 (1982). doi: 10.1137\/0211050","journal-title":"SIAM J. Comput."},{"key":"9944_CR18","volume-title":"Descriptive Complexity","author":"N Immerman","year":"1998","unstructured":"Immerman, N.: Descriptive Complexity. Springer, New York (1998)"},{"issue":"1","key":"9944_CR19","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(76)90068-2","volume":"3","author":"ND Jones","year":"1976","unstructured":"Jones, N.D., Laaser, W.T.: Complete problems for deterministic polynomial time. Theoret. Comput. Sci. 3(1), 105\u2013117 (1976). doi: 10.1016\/0304-3975(76)90068-2","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"9944_CR20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01683259","volume":"10","author":"ND Jones","year":"1976","unstructured":"Jones, N.D., Lien, Y.E., Laaser, W.T.: New problems complete for nondeterministic log space. Math. Syst. Theory 10(1), 1\u201317 (1976). doi: 10.1007\/BF01683259","journal-title":"Math. Syst. Theory"},{"issue":"9","key":"9944_CR21","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1137\/0209003","volume":"1","author":"CMR Kintala","year":"1980","unstructured":"Kintala, C.M.R., Fischer, P.C.: Refining nondeterminism in relativized polynomial-time bounded computations. SIAM J. Comput. 1(9), 46\u201353 (1980). doi: 10.1137\/0209003","journal-title":"SIAM J. Comput."},{"key":"9944_CR22","doi-asserted-by":"crossref","unstructured":"Stockhusen, C., Tantau, T.: Completeness results for parameterized space classes. Tech. Rep. arXiv:1308.2892 , ArXiv e-prints (2013a)","DOI":"10.1007\/978-3-319-03898-8_28"},{"key":"9944_CR23","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/978-3-319-03898-8_28","volume-title":"Parameterized and Exact Computation, Lecture Notes in Computer Science","author":"C Stockhusen","year":"2013","unstructured":"Stockhusen, C., Tantau, T.: Completeness results for parameterized space classes. In: Gutin, G., Szeider, S. (eds.) Parameterized and Exact Computation, Lecture Notes in Computer Science, vol. 8246, pp. 335\u2013347. Springer, Berlin (2013b). doi: 10.1007\/978-3-319-03898-8_28"},{"key":"9944_CR24","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to Circuit Complexity: A Uniform Approach","author":"H Vollmer","year":"1999","unstructured":"Vollmer, H.: Introduction to Circuit Complexity: A Uniform Approach. Springer, Berlin (1999)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9944-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9944-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9944-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,16]],"date-time":"2019-08-16T03:02:44Z","timestamp":1565924564000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9944-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,16]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,3]]}},"alternative-id":["9944"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9944-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,16]]}}}