{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T18:24:57Z","timestamp":1765045497848,"version":"3.37.3"},"reference-count":63,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2023,4,21]],"date-time":"2023-04-21T00:00:00Z","timestamp":1682035200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,4,21]],"date-time":"2023-04-21T00:00:00Z","timestamp":1682035200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004115","name":"Gottfried Wilhelm Leibniz Universit\u00e4t Hannover","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004115","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,10]]},"abstract":"Abstract<\/jats:title>Logarithmic space-bounded complexity classes such as$$\\textbf{L} $$<\/jats:tex-math>L<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and$$\\textbf{NL} $$<\/jats:tex-math>NL<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>play a central role in space-bounded computation. The study of counting versions of these complexity classes have lead to several interesting insights into the structure of computational problems such as computing the determinant and counting paths in directed acyclic graphs. Though parameterised complexity theory was initiated roughly three decades ago by Downey and Fellows, a satisfactory study of parameterised logarithmic space-bounded computation was developed only in the last decade by Elberfeld, Stockhusen and Tantau (IPEC 2013, Algorithmica 2015). In this paper, we introduce a new framework for parameterised counting in logspace, inspired by the parameterised space-bounded models developed by Elberfeld, Stockhusen and Tantau. They defined the operators$$\\textbf{para}_{\\textbf{W}}$$<\/jats:tex-math>para<\/mml:mi>W<\/mml:mi><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and$$\\textbf{para}_\\beta $$<\/jats:tex-math>para<\/mml:mi>\u03b2<\/mml:mi><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>for parameterised space complexity classes by allowing bounded nondeterminism with multiple-read and read-once access, respectively. Using these operators, they characterised the parameterised complexity of natural problems on graphs. In the spirit of the operators$$\\textbf{para}_{\\textbf{W}}$$<\/jats:tex-math>para<\/mml:mi>W<\/mml:mi><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and$$\\textbf{para}_\\beta $$<\/jats:tex-math>para<\/mml:mi>\u03b2<\/mml:mi><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>by Stockhusen and Tantau, we introduce variants based on tail-nondeterminism,$$\\textbf{para}_{{\\textbf{W}}[1]}$$<\/jats:tex-math>para<\/mml:mi>W<\/mml:mi>[<\/mml:mo>1<\/mml:mn>]<\/mml:mo><\/mml:mrow><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and$$\\textbf{para}_{\\beta {\\textbf{tail}}}$$<\/jats:tex-math>para<\/mml:mi>\u03b2<\/mml:mi>tail<\/mml:mi><\/mml:mrow><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Then, we consider counting versions of all four operators and apply them to the class$$\\textbf{L} $$<\/jats:tex-math>L<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We obtain several natural complete problems for the resulting classes: counting of paths in digraphs, counting first-order models for formulas, and counting graph homomorphisms. Furthermore, we show that the complexity of a parameterised variant of the determinant function for (0,\u00a01)-matrices is$$\\#\\textbf{para}_{\\beta {\\textbf{tail}}}\\textbf{L} $$<\/jats:tex-math>#<\/mml:mo>para<\/mml:mi>\u03b2<\/mml:mi>tail<\/mml:mi><\/mml:mrow><\/mml:msub>L<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hard and can be written as the difference of two functions in$$\\#\\textbf{para}_{\\beta {\\textbf{tail}}}\\textbf{L} $$<\/jats:tex-math>#<\/mml:mo>para<\/mml:mi>\u03b2<\/mml:mi>tail<\/mml:mi><\/mml:mrow><\/mml:msub>L<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. These problems exhibit the richness of the introduced counting classes. Our results further indicate interesting structural characteristics of these classes. For example, we show that the closure of$$\\#\\textbf{para}_{\\beta {\\textbf{tail}}}\\textbf{L} $$<\/jats:tex-math>#<\/mml:mo>para<\/mml:mi>\u03b2<\/mml:mi>tail<\/mml:mi><\/mml:mrow><\/mml:msub>L<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>under parameterised logspace parsimonious reductions coincides with$$\\#\\textbf{para}_\\beta \\textbf{L} $$<\/jats:tex-math>#<\/mml:mo>para<\/mml:mi>\u03b2<\/mml:mi><\/mml:msub>L<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. In other words, in the setting of read-once access to nondeterministic bits, tail-nondeterminism coincides with unbounded nondeterminism modulo parameterised reductions. Initiating the study of closure properties of these parameterised logspace counting classes, we show that all introduced classes are closed under addition and multiplication, and those without tail-nondeterminism are closed under parameterised logspace parsimonious reductions. Finally, we want to emphasise the significance of this topic by providing a promising outlook highlighting several open problems and directions for further research.<\/jats:p>","DOI":"10.1007\/s00453-023-01114-2","type":"journal-article","created":{"date-parts":[[2023,4,21]],"date-time":"2023-04-21T06:02:32Z","timestamp":1682056952000},"page":"2923-2961","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Parameterised Counting in Logspace"],"prefix":"10.1007","volume":"85","author":[{"given":"Anselm","family":"Haak","sequence":"first","affiliation":[]},{"given":"Arne","family":"Meier","sequence":"additional","affiliation":[]},{"given":"Om","family":"Prakash","sequence":"additional","affiliation":[]},{"given":"B. V. Raghavendra","family":"Rao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,4,21]]},"reference":[{"key":"1114_CR1","series-title":"Monographs in Computer Science","doi-asserted-by":"publisher","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. Monographs in Computer Science, Springer (1999)"},{"key":"1114_CR2","series-title":"Theory Texts in Theoretical Computer Science. An EATCS Series","volume-title":"Parameterized Complexity","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity. Theory Texts in Theoretical Computer Science. An EATCS Series, Springer (2006)"},{"key":"1114_CR3","doi-asserted-by":"crossref","unstructured":"Stockhusen, C., Tantau, T.: Completeness Results for Parameterized Space Classes. In: IPEC. vol. 8246 of Lecture Notes in Computer Science. Springer; pp. 335\u2013347 (2013)","DOI":"10.1007\/978-3-319-03898-8_28"},{"issue":"3","key":"1114_CR4","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1007\/s00453-014-9944-y","volume":"71","author":"M Elberfeld","year":"2015","unstructured":"Elberfeld, M., Stockhusen, C., Tantau, T.: On the space and circuit complexity of parameterized problems: classes and completeness. Algorithmica 71(3), 661\u2013701 (2015)","journal-title":"Algorithmica"},{"key":"1114_CR5","unstructured":"Bannach, M., Stockhusen, C., Tantau, T.: Fast Parallel Fixed-parameter Algorithms via Color Coding. In: IPEC. vol.\u00a043 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. pp. 224\u2013235 (2015)"},{"issue":"4","key":"1114_CR6","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J ACM 42(4), 844\u2013856 (1995)","journal-title":"J ACM"},{"key":"1114_CR7","unstructured":"Chen, Y., Flum, J.: Some Lower Bounds in Parameterized AC$${}^{\\text{0}}$$. In: MFCS. vol.\u00a058 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik; pp. 27:1\u201327:14 (2016)"},{"key":"1114_CR8","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci. 8, 189\u2013201 (1979)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"1114_CR9","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S Toda","year":"1991","unstructured":"Toda, S.: PP is as hard as the polynomial-time hierarchy. SIAM J. Comput. 20(5), 865\u2013877 (1991)","journal-title":"SIAM J. Comput."},{"key":"1114_CR10","unstructured":"Damm, C.: DET = $$L^{\\#L}$$? Informatik-Preprint 8, Fachbereich Informatik der Humboldt-Universitlt zu Berlin (1991)"},{"key":"1114_CR11","doi-asserted-by":"crossref","unstructured":"Vinay, V.: Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits. In: Proceedings of 6th structure in complexity theory conference. pp. 270\u2013284 (1991)","DOI":"10.1109\/SCT.1991.160269"},{"key":"1114_CR12","unstructured":"Toda, S.: Counting problems computationally equivalent to the determinant. Dept. Comp. Sci. and Inf. Math., Univ. of Electro-Communications, Tokyo. (1991). CSIM 91-07. Available from: http:\/\/perso.ens-lyon.fr\/natacha.portier\/papers\/toda91.pdf"},{"issue":"1","key":"1114_CR13","first-page":"1","volume":"30","author":"E Allender","year":"1996","unstructured":"Allender, E., Ogihara, M.: Relationships among PL, #L, and the determinant. ITA 30(1), 1\u201321 (1996)","journal-title":"ITA"},{"issue":"2","key":"1114_CR14","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/s000370050023","volume":"8","author":"E Allender","year":"1999","unstructured":"Allender, E., Beals, R., Ogihara, M.: The complexity of matrix rank and feasible systems of linear equations. Comput. Complex. 8(2), 99\u2013126 (1999)","journal-title":"Comput. Complex."},{"issue":"2","key":"1114_CR15","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1006\/jcss.1999.1676","volume":"60","author":"R Beigel","year":"2000","unstructured":"Beigel, R., Fu, B.: Circuits over PP and PL. J. Comput. Syst. Sci. 60(2), 422\u2013441 (2000)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"1114_CR16","doi-asserted-by":"publisher","first-page":"1430","DOI":"10.1137\/S0097539795295924","volume":"27","author":"M Ogihara","year":"1998","unstructured":"Ogihara, M., The, P.L.: Hierarchy collapses. SIAM J. Comput. 27(5), 1430\u20131437 (1998)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1114_CR17","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1006\/jcss.1998.1588","volume":"57","author":"H Caussinus","year":"1998","unstructured":"Caussinus, H., McKenzie, P., Th\u00e9rien, D., Vollmer, H.: Nondeterministic $${NC}{}^{\\text{1 }}$$ computation. J. Comput. Syst. Sci. 57(2), 200\u2013212 (1998)","journal-title":"J. Comput. Syst. Sci."},{"key":"1114_CR18","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/j.tcs.2011.05.050","volume":"417","author":"S Datta","year":"2012","unstructured":"Datta, S., Mahajan, M., Rao, B.V.R., Thomas, M., Vollmer, H.: Counting classes and the fine structure between NC$${}^{\\text{1 }}$$ and L. Theor. Comput. Sci. 417, 36\u201349 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"1114_CR19","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1006\/jcss.1999.1675","volume":"60","author":"M Agrawal","year":"2000","unstructured":"Agrawal, M., Allender, E., Datta, S.: On TC$${}^{0}$$, AC$${}^{0}$$, and arithmetic circuits. J. Comput. Syst. Sci. 60(2), 395\u2013421 (2000)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"1114_CR20","doi-asserted-by":"publisher","first-page":"892","DOI":"10.1137\/S0097539703427203","volume":"33","author":"J Flum","year":"2004","unstructured":"Flum, J., Grohe, M.: The parameterized complexity of counting problems. SIAM J. Comput. 33(4), 892\u2013922 (2004)","journal-title":"SIAM J. Comput."},{"key":"1114_CR21","doi-asserted-by":"crossref","unstructured":"McCartin, C.: Parameterized Counting Problems. In: MFCS. vol. 2420 of Lecture Notes in Computer Science. Springer. pp. 556\u2013567 (2002)","DOI":"10.1007\/3-540-45687-2_46"},{"key":"1114_CR22","doi-asserted-by":"crossref","unstructured":"Curticapean, R.: Counting Matchings of Size k Is W[1]-Hard. In: ICALP (1). vol. 7965 of Lecture Notes in Computer Science. Springer. pp. 352\u2013363 (2013)","DOI":"10.1007\/978-3-642-39206-1_30"},{"key":"1114_CR23","unstructured":"Curticapean, R.: The simple, little and slow things count: on parameterized counting complexity [Phd. Thesis]. Saarland University (2015)"},{"key":"1114_CR24","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/j.ic.2018.02.008","volume":"261","author":"R Curticapean","year":"2018","unstructured":"Curticapean, R.: Block interpolation: a framework for tight exponential-time counting complexity. Inf. Comput. 261, 265\u2013280 (2018)","journal-title":"Inf. Comput."},{"key":"1114_CR25","doi-asserted-by":"crossref","unstructured":"Curticapean, R., Dell, H., Marx, D.: Homomorphisms are a good basis for counting small subgraphs. In: STOC. ACM. pp. 210\u2013223 (2017)","DOI":"10.1145\/3055399.3055502"},{"issue":"5","key":"1114_CR26","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1007\/s00493-016-3338-5","volume":"37","author":"M Jerrum","year":"2017","unstructured":"Jerrum, M., Meeks, K.: The parameterised complexity of counting even and odd induced subgraphs. Combinatorica 37(5), 965\u2013990 (2017)","journal-title":"Combinatorica"},{"key":"1114_CR27","doi-asserted-by":"crossref","unstructured":"Brand, C., Roth, M.: Parameterized Counting of Trees, Forests and Matroid Bases. In: CSR. vol. 10304 of Lecture Notes in Computer Science. Springer. pp. 85\u201398 (2017)","DOI":"10.1007\/978-3-319-58747-9_10"},{"key":"1114_CR28","unstructured":"Peyerimhoff, N., Roth, M., Schmitt, J., Stix, J., Vdovina, A.: Parameterized (Modular) Counting and Cayley Graph Expanders. In: MFCS. vol. 202 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik. pp. 84:1\u201384:15 (2021)"},{"key":"1114_CR29","doi-asserted-by":"crossref","unstructured":"Focke, J., Roth, M.: Counting small induced subgraphs with hereditary properties. In: STOC. ACM. pp. 1543\u20131551 (2022)","DOI":"10.1145\/3519935.3520008"},{"key":"1114_CR30","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity - A Modern Approach","author":"S Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity - A Modern Approach. Cambridge University Press, Cambridge (2009)"},{"issue":"2\u20133","key":"1114_CR31","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/j.tcs.2005.02.003","volume":"339","author":"Y Chen","year":"2005","unstructured":"Chen, Y., Flum, J., Grohe, M.: Machine-based methods in parameterized complexity theory. Theor. Comput. Sci. 339(2\u20133), 167\u2013199 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"1114_CR32","doi-asserted-by":"crossref","unstructured":"Chauhan, A., Rao, B.V.R.: Parameterized Analogues of Probabilistic Computation. In: CALDAM. vol. 8959 of Lecture Notes in Computer Science. Springer. pp. 181\u2013192 (2015)","DOI":"10.1007\/978-3-319-14974-5_18"},{"key":"1114_CR33","unstructured":"Mahajan, M., Vinay, V.: Determinant: combinatorics, algorithms, and complexity. Chicago J. Theor. Comput. Sci. (1997)"},{"issue":"1\u20133","key":"1114_CR34","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.tcs.2004.08.008","volume":"329","author":"V Dalmau","year":"2004","unstructured":"Dalmau, V., Jonsson, P.: The complexity of counting homomorphisms seen from the other side. Theor. Comput. Sci. 329(1\u20133), 315\u2013323 (2004)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"1114_CR35","doi-asserted-by":"publisher","first-page":"1:1","DOI":"10.1145\/1206035.1206036","volume":"54","author":"M Grohe","year":"2007","unstructured":"Grohe, M.: The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM. 54(1), 1:1-1:24 (2007)","journal-title":"J. ACM."},{"issue":"2","key":"1114_CR36","doi-asserted-by":"publisher","first-page":"7:1","DOI":"10.1145\/2751316","volume":"7","author":"H Chen","year":"2015","unstructured":"Chen, H., M\u00fcller, M.: The fine classification of conjunctive queries and parameterized logarithmic space. TOCT. 7(2), 7:1-7:27 (2015)","journal-title":"TOCT."},{"key":"1114_CR37","unstructured":"Bottesch, R.: Relativization and Interactive Proof Systems in Parameterized Complexity Theory. In: IPEC. vol.\u00a089 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik. pp. 9:1\u20139:12 (2017)"},{"key":"1114_CR38","unstructured":"Bottesch, R.C.: On W[1]-Hardness as Evidence for Intractability. In: MFCS. vol. 117 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik. pp. 73:1\u201373:15 (2018)"},{"key":"1114_CR39","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1016\/j.dam.2015.06.019","volume":"198","author":"K Meeks","year":"2016","unstructured":"Meeks, K.: The challenges of unbounded treewidth in parameterised subgraph counting problems. Discret. Appl. Math. 198, 170\u2013194 (2016)","journal-title":"Discret. Appl. Math."},{"key":"1114_CR40","doi-asserted-by":"crossref","unstructured":"Alon, N., Dao, P., Hajirasouliha, I., Hormozdiari, F., Sahinalp, S.C.: Biomolecular network motif counting and discovery by color coding. In: ISMB. pp. 241\u2013249 (2008)","DOI":"10.1093\/bioinformatics\/btn163"},{"key":"1114_CR41","doi-asserted-by":"crossref","unstructured":"Brand, C., Dell, H., Husfeldt, T.: Extensor-coding. In: STOC. ACM. pp. 151\u2013164 (2018)","DOI":"10.1145\/3188745.3188902"},{"key":"1114_CR42","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/j.tcs.2018.06.049","volume":"755","author":"A Leitert","year":"2019","unstructured":"Leitert, A., Dragan, F.F.: Parameterized approximation algorithms for some location problems in graphs. Theor. Comput. Sci. 755, 48\u201364 (2019)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"1114_CR43","doi-asserted-by":"publisher","first-page":"11:1","DOI":"10.1145\/3389390","volume":"12","author":"AA Bulatov","year":"2020","unstructured":"Bulatov, A.A., Zivn\u00fd, S.: Approximate counting CSP seen from the other side. ACM Trans. Comput. Theory. 12(2), 11:1-11:19 (2020)","journal-title":"ACM Trans. Comput. Theory."},{"key":"1114_CR44","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Saurabh, S., Zehavi, M.: Efficient Computation of Representative Weight Functions with Applications to Parameterized Counting (Extended Version). In: SODA. SIAM. pp. 179\u2013198 (2021)","DOI":"10.1137\/1.9781611976465.13"},{"issue":"4","key":"1114_CR45","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1137\/19M130604X","volume":"51","author":"H Dell","year":"2022","unstructured":"Dell, H., Lapinskas, J., Meeks, K.: Approximately counting and sampling small witnesses using a colorful decision oracle. SIAM J. Comput. 51(4), 849\u2013899 (2022)","journal-title":"SIAM J. Comput."},{"key":"1114_CR46","doi-asserted-by":"crossref","unstructured":"Chen, H., Mengel, S.: Counting Answers to Existential Positive Queries: A Complexity Classification. In: PODS. ACM. pp. 315\u2013326 (2016)","DOI":"10.1145\/2902251.2902279"},{"issue":"4","key":"1114_CR47","doi-asserted-by":"publisher","first-page":"1202","DOI":"10.1007\/s00224-014-9543-y","volume":"57","author":"A Durand","year":"2015","unstructured":"Durand, A., Mengel, S.: Structural tractability of counting of solutions to conjunctive queries. Theory Comput. Syst. 57(4), 1202\u20131249 (2015)","journal-title":"Theory Comput. Syst."},{"key":"1114_CR48","unstructured":"Haak, A., Meier, A., Prakash, O., Rao, B.V.R.: Parameterised Counting in Logspace. In: STACS. vol. 187 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik. pp. 40:1\u201340:17 (2021)"},{"key":"1114_CR49","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory, 4th Edition. vol. 173 of Graduate texts in mathematics. Springer (2012)","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"1114_CR50","doi-asserted-by":"crossref","unstructured":"Chen, Y., Flum, J., Grohe, M.: Bounded nondeterminism and alternation in parameterized complexity theory. In: Computational Complexity Conference. IEEE Computer Society. pp. 13\u201329 (2003)","DOI":"10.1109\/CCC.2003.1214407"},{"key":"1114_CR51","unstructured":"Stockhusen, C.: On the space and circuit complexity of parameterized problems [Phd. Thesis]. University of L\u00fcbeck, Germany. (2017). Available from: http:\/\/www.zhb.uni-luebeck.de\/epubs\/ediss1780.pdf"},{"issue":"2","key":"1114_CR52","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. Inf. Comput. 187(2), 291\u2013319 (2003)","journal-title":"Inf. Comput."},{"key":"1114_CR53","doi-asserted-by":"crossref","unstructured":"Ebbinghaus, H., Flum, J., Thomas, W.: Mathematical logic (2. ed.). Undergraduate texts in mathematics. Springer (1994)","DOI":"10.1007\/978-1-4757-2355-7"},{"issue":"6","key":"1114_CR54","doi-asserted-by":"publisher","first-page":"716","DOI":"10.1145\/602220.602222","volume":"49","author":"J Flum","year":"2002","unstructured":"Flum, J., Frick, M., Grohe, M.: Query evaluation via tree-decompositions. J. ACM 49(6), 716\u2013752 (2002)","journal-title":"J. ACM"},{"key":"1114_CR55","doi-asserted-by":"crossref","unstructured":"Jerrum, M.: Counting, Sampling and Integrating: Algorithms and Complexity. Lectures in Mathematics. Birkh\u00e4user Basel (2003)","DOI":"10.1007\/978-3-0348-8005-3"},{"key":"1114_CR56","unstructured":"Curticapean, R.: Counting Problems in Parameterized Complexity. In: Paul, C., Pilipczuk, M. (eds.) 13th international symposium on parameterized and exact computation (IPEC 2018). vol. 115 of Leibniz international proceedings in informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik. (2019). p. 1:1\u20131:18. Available from: http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2019\/10202"},{"key":"1114_CR57","volume-title":"Introduction to the Theory of Computation","author":"M Sipser","year":"1997","unstructured":"Sipser, M.: Introduction to the Theory of Computation. PWS Publishing Company, Boston (1997)"},{"issue":"3","key":"1114_CR58","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1016\/0022-0000(88)90034-7","volume":"36","author":"JF Buss","year":"1988","unstructured":"Buss, J.F.: Relativized alternation and space-bounded computation. J. Comput. Syst. Sci. 36(3), 351\u2013378 (1988)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"1114_CR59","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0022-0000(93)90006-I","volume":"46","author":"M Ogiwara","year":"1993","unstructured":"Ogiwara, M., Hemachandra, L.A.: A complexity theory for feasible closure properties. J. Comput. Syst. Sci. 46(3), 295\u2013325 (1993). https:\/\/doi.org\/10.1016\/0022-0000(93)90006-I","journal-title":"J. Comput. Syst. Sci."},{"key":"1114_CR60","doi-asserted-by":"crossref","unstructured":"Allender, E., Ambainis, A., Barrington, D.A.M., Datta, S., LeThanh, H.: Bounded depth arithmetic circuits: counting and closure. In: Proceedings of the 26th international colloquium on automata, languages and programming. ICAL \u201999. Berlin, Heidelberg: Springer-Verlag. pp. 149-158 (1999)","DOI":"10.1007\/3-540-48523-6_12"},{"issue":"3","key":"1114_CR61","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1016\/j.tcs.2005.03.012","volume":"340","author":"A Durand","year":"2005","unstructured":"Durand, A., Hermann, M., Kolaitis, P.G.: Subtractive reductions and complete problems for counting complexity classes. Theor. Comput. Sci. 340(3), 496\u2013513 (2005). https:\/\/doi.org\/10.1016\/j.tcs.2005.03.012","journal-title":"Theor. Comput. Sci."},{"issue":"3\u20134","key":"1114_CR62","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<260::AID-RSA5>3.0.CO;2-W","volume":"17","author":"ME Dyer","year":"2000","unstructured":"Dyer, M.E., Greenhill, C.S.: The complexity of counting graph homomorphisms. Random Struct. Algorithms. 17(3\u20134), 260\u2013289 (2000)","journal-title":"Random Struct. Algorithms."},{"issue":"1","key":"1114_CR63","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/S0022-0000(05)80024-8","volume":"48","author":"SA Fenner","year":"1994","unstructured":"Fenner, S.A., Fortnow, L., Kurtz, S.A.: Gap-definable counting classes. J. Comput. Syst. Sci. 48(1), 116\u2013148 (1994)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01114-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01114-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01114-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,18]],"date-time":"2024-10-18T23:04:33Z","timestamp":1729292673000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01114-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,21]]},"references-count":63,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["1114"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01114-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2023,4,21]]},"assertion":[{"value":"2 June 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 March 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 April 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}