{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T21:43:06Z","timestamp":1725745386786},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642406621"},{"type":"electronic","value":"9783642406638"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40663-8_7","type":"book-chapter","created":{"date-parts":[[2013,8,19]],"date-time":"2013-08-19T21:03:57Z","timestamp":1376946237000},"page":"60-73","source":"Crossref","is-referenced-by-count":1,"title":["The Algebraic Theory of Parikh Automata"],"prefix":"10.1007","author":[{"given":"Micha\u00ebl","family":"Cadilhac","sequence":"first","affiliation":[]},{"given":"Andreas","family":"Krebs","sequence":"additional","affiliation":[]},{"given":"Pierre","family":"McKenzie","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"7_CR1","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/s00224-003-1077-7","volume":"36","author":"E. Allender","year":"2003","unstructured":"Allender, E., Arvind, V., Mahajan, M.: Arithmetic complexity, Kleene closure, and formal power series. Theory Comput. Syst.\u00a036(4), 303\u2013328 (2003)","journal-title":"Theory Comput. Syst."},{"key":"7_CR2","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D.A.M. Barrington","year":"1989","unstructured":"Barrington, D.A.M.: Bounded-width polynomial size branching programs recognize exactly those languages in NC1. J. Computer and System Sciences\u00a038, 150\u2013164 (1989)","journal-title":"J. Computer and System Sciences"},{"key":"7_CR3","doi-asserted-by":"publisher","first-page":"941","DOI":"10.1145\/48014.63138","volume":"35","author":"D.A.M. Barrington","year":"1988","unstructured":"Barrington, D.A.M., Th\u00e9rien, D.: Finite monoids and the fine structure of NC1. J. Association of Computing Machinery\u00a035, 941\u2013952 (1988)","journal-title":"J. Association of Computing Machinery"},{"issue":"3","key":"7_CR4","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"D.A.M. Barrington","year":"1990","unstructured":"Barrington, D.A.M., Immerman, N., Straubing, H.: On uniformity within NC1. J. Comput. Syst. Sci.\u00a041(3), 274\u2013306 (1990)","journal-title":"J. Comput. Syst. Sci."},{"key":"7_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/978-3-540-74456-6_15","volume-title":"Mathematical Foundations of Computer Science 2007","author":"C. Behle","year":"2007","unstructured":"Behle, C., Krebs, A., Mercer, M.: Linear circuits, two-variable logic and weakly blocked monoids. In: Ku\u010dera, L., Ku\u010dera, A. (eds.) MFCS 2007. LNCS, vol.\u00a04708, pp. 147\u2013158. Springer, Heidelberg (2007)"},{"key":"7_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/978-3-642-21493-6_6","volume-title":"Algebraic Informatics","author":"C. Behle","year":"2011","unstructured":"Behle, C., Krebs, A., Reifferscheid, S.: Typed monoids - an Eilenberg-like theorem for non regular languages. In: Winkler, F. (ed.) CAI 2011. LNCS, vol.\u00a06742, pp. 97\u2013114. Springer, Heidelberg (2011)"},{"key":"7_CR7","doi-asserted-by":"crossref","unstructured":"Berstel, J., Reutenauer, C.: Noncommutative Rational Series with Applications. Encyclopedia of Mathematics and its Applications. Cambridge University Press (2010)","DOI":"10.1017\/CBO9780511760860"},{"key":"7_CR8","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1002\/malq.19600060105","volume":"6","author":"J.R. B\u00fcchi","year":"1960","unstructured":"B\u00fcchi, J.R.: Weak second order arithmetic and finite automata. Z. Math. Logik Grundlagen Math.\u00a06, 66\u201392 (1960)","journal-title":"Z. Math. Logik Grundlagen Math."},{"key":"7_CR9","doi-asserted-by":"crossref","unstructured":"Cadilhac, M., Finkel, A., McKenzie, P.: Bounded Parikh automata. In: Proc. 8th Internat. Conference on Words. EPTCS, vol.\u00a063, pp. 93\u2013102 (2011)","DOI":"10.4204\/EPTCS.63.13"},{"issue":"4","key":"7_CR10","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\u00a046(4), 511\u2013545 (2012)","journal-title":"RAIRO - Theoretical Informatics and Applications"},{"key":"7_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/978-3-642-31653-1_22","volume-title":"Developments in Language Theory","author":"M. Cadilhac","year":"2012","unstructured":"Cadilhac, M., Finkel, A., McKenzie, P.: Unambiguous constrained automata. In: Yen, H.-C., Ibarra, O.H. (eds.) DLT 2012. LNCS, vol.\u00a07410, pp. 239\u2013250. Springer, Heidelberg (2012)"},{"key":"7_CR12","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 NC1 computation. J. Computer and System Sciences\u00a057, 200\u2013212 (1998)","journal-title":"J. Computer and System Sciences"},{"key":"7_CR13","unstructured":"Eilenberg, S.: Automata, Languages, and Machines. Pure and Applied Mathematics, vol.\u00a0B. Academic Press (1976)"},{"key":"7_CR14","unstructured":"Enderton, H.B.: A Mathematical Introduction to Logic. Academic Press (1972)"},{"issue":"4","key":"7_CR15","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/BF01890611","volume":"7","author":"M. Fliess","year":"1974","unstructured":"Fliess, M.: Propri\u00e9t\u00e9s bool\u00e9ennes des langages stochastiques. Mathematical Systems Theory\u00a07(4), 353\u2013359 (1974)","journal-title":"Mathematical Systems Theory"},{"key":"7_CR16","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J. Gill","year":"1977","unstructured":"Gill, J.: Computational complexity of probabilistic turing machines. SIAM J. Computing\u00a06, 675\u2013695 (1977)","journal-title":"SIAM J. Computing"},{"issue":"2","key":"7_CR17","doi-asserted-by":"publisher","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. Pacific J. Mathematics\u00a016(2), 285\u2013296 (1966)","journal-title":"Pacific J. Mathematics"},{"key":"7_CR18","unstructured":"Karianto, W.: Parikh automata with pushdown stack. PhD thesis, RWTH Aachen (2004)"},{"key":"7_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1007\/3-540-45061-0_54","volume-title":"Automata, Languages and Programming","author":"F. Klaedtke","year":"2003","unstructured":"Klaedtke, F., Rue\u00df, H.: Monadic second-order logics with cardinalities. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 681\u2013696. Springer, Heidelberg (2003)"},{"issue":"4","key":"7_CR20","doi-asserted-by":"publisher","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\u00a040(4), 303\u2013325 (2007)","journal-title":"Theory of Computing Systems"},{"issue":"3","key":"7_CR21","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/s00224-009-9233-3","volume":"46","author":"N. Limaye","year":"2010","unstructured":"Limaye, N., Mahajan, M., Rao, B.V.R.: Arithmetizing classes around NC1 and L. Theory Comput. Syst.\u00a046(3), 499\u2013522 (2010)","journal-title":"Theory Comput. Syst."},{"issue":"4","key":"7_CR22","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1145\/321356.321364","volume":"13","author":"R.J. Parikh","year":"1966","unstructured":"Parikh, R.J.: On context-free languages. J. ACM\u00a013(4), 570\u2013581 (1966)","journal-title":"J. ACM"},{"key":"7_CR23","doi-asserted-by":"publisher","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":"7_CR24","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0289-9","volume-title":"Finite Automata, Formal Logic, and Circuit Complexity","author":"H. Straubing","year":"1994","unstructured":"Straubing, H.: Finite Automata, Formal Logic, and Circuit Complexity. Birkh\u00e4user, Basel (1994)"},{"issue":"3","key":"7_CR25","doi-asserted-by":"publisher","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. Information and Control\u00a018(3), 253\u2013256 (1971)","journal-title":"Information and Control"},{"key":"7_CR26","doi-asserted-by":"crossref","unstructured":"Vollmer, H.: Introduction to Circuit Complexity \u2013 A Uniform Approach. Texts in Theoretical Computer Science. Springer (1999)","DOI":"10.1007\/978-3-662-03927-4"}],"container-title":["Lecture Notes in Computer Science","Algebraic Informatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40663-8_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T21:55:01Z","timestamp":1558302901000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40663-8_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642406621","9783642406638"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40663-8_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}
