{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T06:29:40Z","timestamp":1762324180770,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2017,11,7]],"date-time":"2017-11-07T00:00:00Z","timestamp":1510012800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Chaire Digiteo, ENS Cachan - \u00c9cole Polytechnique"},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["KR 4042\/2"],"award-info":[{"award-number":["KR 4042\/2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,7]]},"DOI":"10.1007\/s00224-017-9817-2","type":"journal-article","created":{"date-parts":[[2017,11,7]],"date-time":"2017-11-07T01:18:24Z","timestamp":1510017504000},"page":"1241-1268","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["The Algebraic Theory of Parikh Automata"],"prefix":"10.1007","volume":"62","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9828-9129","authenticated-orcid":false,"given":"Micha\u00ebl","family":"Cadilhac","sequence":"first","affiliation":[]},{"given":"Andreas","family":"Krebs","sequence":"additional","affiliation":[]},{"given":"Pierre","family":"McKenzie","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,11,7]]},"reference":[{"key":"9817_CR1","doi-asserted-by":"publisher","unstructured":"Abdulla, P.A., Atig, M.F., Meyer, R., Salehi, M.S.: What\u2019s Decidable about Availability Languages. In: FSTTCS, LIPIcs, vol. 45, pp. 192\u2013205. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2015). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2015.192","DOI":"10.4230\/LIPIcs.FSTTCS.2015.192"},{"key":"9817_CR2","doi-asserted-by":"publisher","unstructured":"Akshay, S., Genest, B., Karelovic, B., Vyas, N.: On Regularity of Unary Probabilistic Automata. In: STACS, LIPIcs, vol. 47, pp. 8:1\u20138:14. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2016). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2016.8","DOI":"10.4230\/LIPIcs.STACS.2016.8"},{"key":"9817_CR3","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"DAM Barrington","year":"1989","unstructured":"Barrington, D.A.M.: Bounded-width polynomial size branching programs recognize exactly those languages in NC1. J. Comput. Syst. Sci. 38, 150\u2013164 (1989)","journal-title":"J. Comput. Syst. Sci."},{"key":"9817_CR4","doi-asserted-by":"crossref","first-page":"941","DOI":"10.1145\/48014.63138","volume":"35","author":"DAM Barrington","year":"1988","unstructured":"Barrington, D.A.M., Th\u00e9rien, D.: Finite monoids and the fine structure of NC1. J. Assoc. Comput. Mach. 35, 941\u2013952 (1988)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9817_CR5","doi-asserted-by":"crossref","unstructured":"Behle, C., Krebs, A., Mercer, M.: Linear Circuits, Two-Variable Logic and Weakly Blocked Monoids. In: Mathematical Foundations of Computer Science, LNCS, vol. 4708, pp. 147\u2013158. Springer, Berlin (2007)","DOI":"10.1007\/978-3-540-74456-6_15"},{"key":"9817_CR6","doi-asserted-by":"crossref","unstructured":"Behle, C., Krebs, A., Reifferscheid, S.: Typed Monoids - an Eilenberg-Like Theorem for Non Regular Languages. In: Algebraic Informatics, LNCS, vol. 6742, pp. 97\u2013114. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-21493-6_6"},{"key":"9817_CR7","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511760860","volume-title":"Noncommutative Rational Series with Applications. Encyclopedia of Mathematics and its Applications","author":"J Berstel","year":"2010","unstructured":"Berstel, J., Reutenauer, C.: Noncommutative Rational Series with Applications. Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge (2010)"},{"key":"9817_CR8","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1002\/malq.19600060105","volume":"6","author":"JR Bu\u0307chi","year":"1960","unstructured":"Bu\u0307chi, J. R.: Weak second order arithmetic and finite automata. Z. Math. Logik Grundlagen Math. 6, 66\u201392 (1960)","journal-title":"Z. Math. Logik Grundlagen Math."},{"issue":"04","key":"9817_CR9","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1051\/ita\/2012013","volume":"46","author":"M Cadilhac","year":"2012","unstructured":"Cadilhac, M., Finkel, A., McKenzie, P.: Affine Parikh automata. RAIRO - Theoretical Informatics and Applications 46(04), 511\u2013545 (2012). https:\/\/doi.org\/10.1051\/ita\/2012013","journal-title":"RAIRO - Theoretical Informatics and Applications"},{"issue":"08","key":"9817_CR10","doi-asserted-by":"crossref","first-page":"1691","DOI":"10.1142\/S0129054112400709","volume":"23","author":"M Cadilhac","year":"2012","unstructured":"Cadilhac, M., Finkel, A., McKenzie, P.: Bounded Parikh automata. Int. J. Found. Comput. Sci. 23(08), 1691\u20131709 (2012)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"7","key":"9817_CR11","doi-asserted-by":"publisher","first-page":"1099","DOI":"10.1142\/S0129054113400339","volume":"24","author":"M Cadilhac","year":"2013","unstructured":"Cadilhac, M., Finkel, A., McKenzie, P.: Unambiguous constrained automata. Int. J. Found. Comput. Sci. 24(7), 1099\u20131116 (2013). https:\/\/doi.org\/10.1142\/S0129054113400339","journal-title":"Int. J. Found. Comput. Sci."},{"key":"9817_CR12","doi-asserted-by":"crossref","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 NC1 computation. J. Comput. Syst. Sci. 57, 200\u2013212 (1998)","journal-title":"J. Comput. Syst. Sci."},{"key":"9817_CR13","doi-asserted-by":"publisher","unstructured":"Chomsky, N., Sch\u00fctzenberger, M.P.: The Algebraic Theory of Context-Free Languages. In: Computer Programming and Formal Systems, Studies in Logic and the Foundations of Mathematics, vol. 26, pp. 118\u2013161. Elsevier, Amsterdam (1959). https:\/\/doi.org\/10.1016\/S0049-237X(09)70104-1","DOI":"10.1016\/S0049-237X(09)70104-1"},{"key":"9817_CR14","volume-title":"Automata, Languages, and Machines, Volume B. Pure and Applied Mathematics","author":"S Eilenberg","year":"1976","unstructured":"Eilenberg, S.: Automata, Languages, and Machines, Volume B. Pure and Applied Mathematics. Academic Press, Cambridge (1976)"},{"key":"9817_CR15","volume-title":"A mathematical introduction to logic","author":"HB Enderton","year":"1972","unstructured":"Enderton, H.B.: A mathematical introduction to logic. Academic Press, Cambridge (1972)"},{"key":"9817_CR16","doi-asserted-by":"publisher","unstructured":"Figueira, D., Libkin, L.: Path Logics for Querying Graphs: combining Expressiveness and Efficiency. In: LICS, pp. 329\u2013340 (2015). https:\/\/doi.org\/10.1109\/LICS.2015.39","DOI":"10.1109\/LICS.2015.39"},{"issue":"5","key":"9817_CR17","doi-asserted-by":"publisher","first-page":"1043","DOI":"10.2307\/2036087","volume":"17","author":"S Ginsburg","year":"1966","unstructured":"Ginsburg, S., Spanier, E.H.: Bounded regular sets. Proc. Am. Math. Soc. 17(5), 1043\u20131049 (1966). https:\/\/doi.org\/10.2307\/2036087","journal-title":"Proc. Am. Math. Soc."},{"issue":"2","key":"9817_CR18","doi-asserted-by":"crossref","first-page":"285","DOI":"10.2140\/pjm.1966.16.285","volume":"16","author":"S Ginsburg","year":"1966","unstructured":"Ginsburg, S., Spanier, E.H.: Semigroups, Presburger formulas and languages. Pac. J. Math. 16(2), 285\u2013296 (1966)","journal-title":"Pac. J. Math."},{"key":"9817_CR19","doi-asserted-by":"crossref","unstructured":"Hoenicke, J., Meyer, R., Olderog, E.R.: Kleene, Rabin, and Scott are Available. In: Proceedings of the 21St International Conference on Concurrency Theory, CONCUR\u201910, pp. 462\u2013477. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-15375-4_32"},{"issue":"1","key":"9817_CR20","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1145\/322047.322058","volume":"25","author":"OH Ibarra","year":"1978","unstructured":"Ibarra, O.H.: Reversal-bounded multicounter machines and their decision problems. J. ACM 25(1), 116\u2013133 (1978). https:\/\/doi.org\/10.1145\/322047.322058","journal-title":"J. ACM"},{"issue":"1","key":"9817_CR21","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1080\/00927870802243580","volume":"37","author":"M Kambites","year":"2009","unstructured":"Kambites, M.: Formal languages and groups as memory. Commun. Algebra 37(1), 193\u2013208 (2009). https:\/\/doi.org\/10.1080\/00927870802243580","journal-title":"Commun. Algebra"},{"key":"9817_CR22","unstructured":"Karianto, W.: Parikh automata with pushdown stack. Diploma thesis RWTH Aachen (2004)"},{"key":"9817_CR23","doi-asserted-by":"publisher","unstructured":"Klaedtke, F., Rue\u00df, H.: Monadic second-order logics with cardinalities. In: International Colloquium on Automata, Languages and Programming, LNCS, vol. 2719, pp. 681\u2013696. Springer, Berlin (2003). https:\/\/doi.org\/10.1007\/3-540-45061-0_54","DOI":"10.1007\/3-540-45061-0_54"},{"key":"9817_CR24","volume-title":"Typed Semigroups, Majority Logic, and Threshold Circuits","author":"A Krebs","year":"2008","unstructured":"Krebs, A.: Typed Semigroups, Majority Logic, and Threshold Circuits. Ph.D. thesis, Eberhard Karls University of T\u00fcbingen (2008)"},{"issue":"4","key":"9817_CR25","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/s00224-006-1310-2","volume":"40","author":"A Krebs","year":"2007","unstructured":"Krebs, A., Lange, K.J., Reifferscheid, S.: Characterizing TC0 in terms of infinite groups. Theory of Computing Systems 40(4), 303\u2013325 (2007)","journal-title":"Theory of Computing Systems"},{"issue":"4","key":"9817_CR26","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1145\/321356.321364","volume":"13","author":"RJ Parikh","year":"1966","unstructured":"Parikh, R.J.: On context-free languages. J. ACM 13(4), 570\u2013581 (1966). https:\/\/doi.org\/10.1145\/321356.321364","journal-title":"J. ACM"},{"key":"9817_CR27","unstructured":"Pin, J.E.: Mathematical foundations of automata theory (2016). https:\/\/www.irif.fr\/~jep\/PDF\/MPRI\/MPRI.pdf"},{"key":"9817_CR28","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-6264-0","volume-title":"Automata-Theoretic Aspects of Formal Power Series","author":"A Salomaa","year":"1978","unstructured":"Salomaa, A., Soittola, M.: Automata-Theoretic Aspects of Formal Power Series. Springer, New York (1978)"},{"key":"9817_CR29","doi-asserted-by":"publisher","unstructured":"Straubing, H.: Finite Automata, Formal Logic, and Circuit Complexity. Birk\u00e4user, Boston 1994. https:\/\/doi.org\/10.1007\/978-1-4612-0289-9","DOI":"10.1007\/978-1-4612-0289-9"},{"issue":"3","key":"9817_CR30","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/S0019-9958(71)90391-3","volume":"18","author":"P Turakainen","year":"1971","unstructured":"Turakainen, P.: Some closure properties of the family of stochastic languages. Inf. Control. 18(3), 253\u2013256 (1971)","journal-title":"Inf. Control."},{"key":"9817_CR31","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to circuit complexity","author":"H Vollmer","year":"1999","unstructured":"Vollmer, H.: Introduction to circuit complexity. Springer, Berlin (1999)"},{"key":"9817_CR32","unstructured":"Zare, D.: For a linear recurrence sequence (u n ) n\u2265\u20090, can {i|u i >\u20090} be the set of Fibonacci numbers? MathOverflow (2015). http:\/\/mathoverflow.net\/q\/222379"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9817-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9817-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9817-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,5]],"date-time":"2019-10-05T14:37:51Z","timestamp":1570286271000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9817-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,7]]},"references-count":32,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["9817"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9817-2","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2017,11,7]]}}}