{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,24]],"date-time":"2026-07-24T06:16:29Z","timestamp":1784873789398,"version":"3.55.0"},"reference-count":27,"publisher":"EDP Sciences","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"published-print":{"date-parts":[[2012,10]]},"DOI":"10.1051\/ita\/2012013","type":"journal-article","created":{"date-parts":[[2012,8,2]],"date-time":"2012-08-02T10:47:04Z","timestamp":1343904424000},"page":"511-545","source":"Crossref","is-referenced-by-count":19,"title":["Affine Parikh automata"],"prefix":"10.1051","volume":"46","author":[{"given":"Micha\u00ebl","family":"Cadilhac","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alain","family":"Finkel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pierre","family":"McKenzie","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"250","published-online":{"date-parts":[[2012,8,2]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Baker B.S. and Book R.V., Reversal-bounded multipushdown machines.J. Comput. Syst. Sci.8(1974) 315\u2013332.","DOI":"10.1016\/S0022-0000(74)80027-9"},{"key":"R2","unstructured":"Blattner M. and Latteux M., Parikh-bounded languages, in ICALP.Lect. Notes Comput. Sci.115(1981) 316\u2013323."},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Book R., Nivat M. and Paterson M., Reversal-bounded acceptors and intersections of linear languages.SIAM J. Comput.3(1974) 283.","DOI":"10.1137\/0203023"},{"key":"R4","unstructured":"Brandenburg F., Analogies of PAL and COPY, in Fundamentals of Computation Theory.Lect. Notes in Comput. Sci.117(1981) 61\u201370."},{"key":"R5","unstructured":"E. Chiniforooshan, M. Daley, O.H. Ibarra, L. Kari and S. Seki, One-reversal counter machines and multihead automata : revisited, in Proc. ofSOFSEM. ACM (2011) 166\u2013177."},{"key":"R6","unstructured":"H.B. Enderton,A Mathematical Introduction to Logic. Academic Press (1972)."},{"key":"R7","unstructured":"Ferrante J. and Rackoff C., A decision procedure for the first order theory of real addition with order.SIAM J. Comput.4(1975) 69\u201376."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"Ganty P., Majumdar R. and Monmege B., Bounded underapproximations.Form. Methods Syst. Des.40(2012) 206\u2013231.","DOI":"10.1007\/s10703-011-0136-y"},{"key":"R9","unstructured":"Ginsburg S. and Spanier E.H., Semigroups, Presburger formulas and languages.Pacific J. Math.16(1966) 285\u2013296."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Ginsburg S. and Spanier E., Finite-turn pushdown automata.SIAM J. Control Optim.4(1966) 429.","DOI":"10.1137\/0304034"},{"key":"R11","unstructured":"Greibach S.A., A note on undecidable properties of formal languages.Math. Syst. Theor.2(1968) 1\u20136."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"Ibarra O.H., Reversal-bounded multicounter machines and their decision problems.J. ACM25(1978) 116\u2013133.","DOI":"10.1145\/322047.322058"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"Ibarra O.H. and Su J., A technique for proving decidability of containment and equivalence of linear constraint queries.J. Comput. Syst. Sci.59(1999) 1\u201328.","DOI":"10.1006\/jcss.1999.1624"},{"key":"R14","unstructured":"Ibarra O.H., Su J., Dang Z., Bultan T. and Kemmerer R.A., Counter machines and verification problems.Theor. Comput. Sci.289(2002) 165\u2013189."},{"key":"R15","unstructured":"W. Karianto,Parikh automata with pushdown stack. Diploma thesis, RWTH Aachen (2004)."},{"key":"R16","doi-asserted-by":"crossref","unstructured":"F. Klaedtke and H. Rue\u00df,Parikh automata and monadic second-order logics with linear cardinality constraints. Universit\u00e4t Freiburg, Tech. Rep. 177 (2002).","DOI":"10.1007\/3-540-45061-0_54"},{"key":"R17","unstructured":"Klaedtke F. and Rue\u00df H., Monadic second-order logics with cardinalities, in Proc. of ICALP.Lect. Notes Comput. Sci.2719(2003) 681\u2013696."},{"key":"R18","doi-asserted-by":"crossref","unstructured":"Kuroda S.Y., Classes of languages and linear bounded automata.Inform. Control7(1964) 207\u2013223.","DOI":"10.1016\/S0019-9958(64)90120-2"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"Latteux M., Mots infinis et langages commutatifs.RAIRO Inform. Th\u00e9or. Appl.12(1978) 185\u2013192.","DOI":"10.1051\/ita\/1978120301851"},{"key":"R20","unstructured":"D.R. Mazur,Combinatorics : A Guided Tour. Mathematical Association of Mathematics (2010)."},{"key":"R21","unstructured":"McKenzie P., Thomas M. and Vollmer H., Extensional uniformity for boolean circuits.SIAM J. Comput.39(2010) 3186\u20133206."},{"key":"R22","doi-asserted-by":"crossref","unstructured":"H. Seidl, T. Schwentick and A. Muscholl, Numerical document queries, inPrinciples of Database Systems. ACM, San Diego, CA, USA (2003) 155\u2013166.","DOI":"10.1145\/773153.773169"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"H. Straubing,Finite Automata, Formal Logic, and Circuit Complexity. Birkh\u00e4user, Boston (1994).","DOI":"10.1007\/978-1-4612-0289-9"},{"key":"R24","unstructured":"Tesson P. and Th\u00e9rien D., Logic meets algebra : the case of regular languages.Log. Meth. Comput. Sci.3(2007) 1\u201337."},{"key":"R25","doi-asserted-by":"crossref","unstructured":"L.P.D. van den Dries,Tame Topology and O-minimal Structures. Cambridge Univ. Press (1998).","DOI":"10.1017\/CBO9780511525919"},{"key":"R26","unstructured":"Wolper P. and Boigelot B., An automata-theoretic approach to Presburger arithmetic constraints, in Static Analysis (SAS\u201995).Lect. Notes Comput. Sci.983(1995) 21\u201332."},{"key":"R27","doi-asserted-by":"crossref","unstructured":"S.D. Zilio and D. Lugiez, Xml schema, tree logic and sheaves automata, inRewriting Techniques and Applications(2003) 246\u2013263.","DOI":"10.1007\/3-540-44881-0_18"}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/2012013\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,2]],"date-time":"2019-07-02T08:21:47Z","timestamp":1562055707000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/2012013"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8,2]]},"references-count":27,"journal-issue":{"issue":"4"},"alternative-id":["ita110030"],"URL":"https:\/\/doi.org\/10.1051\/ita\/2012013","relation":{},"ISSN":["0988-3754","1290-385X"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"1290-385X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,8,2]]}}}