Affine Parikh automata
Cadilhac, Michaël ; Finkel, Alain ; McKenzie, Pierre
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012), p. 511-545 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

The Parikh finite word automaton (PA) was introduced and studied in 2003 by Klaedtke and Rueß. Natural variants of the PA arise from viewing a PA equivalently as an automaton that keeps a count of its transitions and semilinearly constrains their numbers. Here we adopt this view and define the affine PA, that extends the PA by having each transition induce an affine transformation on the PA registers, and the PA on letters, that restricts the PA by forcing any two transitions on the same letter to affect the registers equally. Then we report on the expressiveness, closure, and decidability properties of such PA variants. We note that deterministic PA are strictly weaker than deterministic reversal-bounded counter machines.

Publié le : 2012-01-01
DOI : https://doi.org/10.1051/ita/2012013
Classification:  68Q45 
@article{ITA_2012__46_4_511_0,
     author = {Cadilhac, Micha\"el and Finkel, Alain and McKenzie, Pierre},
     title = {Affine Parikh automata},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {46},
     year = {2012},
     pages = {511-545},
     doi = {10.1051/ita/2012013},
     mrnumber = {3107862},
     zbl = {1279.68136},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2012__46_4_511_0}
}

Cadilhac, Michaël; Finkel, Alain; McKenzie, Pierre. Affine Parikh automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) pp. 511-545. doi : 10.1051/ita/2012013. http://gdmltest.u-ga.fr/item/ITA_2012__46_4_511_0/

[1] B.S. Baker and R.V. Book, Reversal-bounded multipushdown machines. J. Comput. Syst. Sci. 8 (1974) 315-332. | MR 375844 | Zbl 0309.68043

[2] M. Blattner and M. Latteux, Parikh-bounded languages, in ICALP. Lect. Notes Comput. Sci. 115 (1981) 316-323. | MR 635146 | Zbl 0462.68057

[3] R. Book, M. Nivat and M. Paterson, Reversal-bounded acceptors and intersections of linear languages. SIAM J. Comput. 3 (1974) 283. | MR 433992 | Zbl 0292.68023

[4] F. Brandenburg, Analogies of PAL and COPY, in Fundamentals of Computation Theory. Lect. Notes in Comput. Sci. 117 (1981) 61-70. | MR 652970 | Zbl 0462.68058

[5] E. Chiniforooshan, M. Daley, O.H. Ibarra, L. Kari and S. Seki, One-reversal counter machines and multihead automata : revisited, in Proc. of SOFSEM. ACM (2011) 166-177. | MR 2804119 | Zbl 1298.68127

[6] H.B. Enderton, A Mathematical Introduction to Logic. Academic Press (1972). | MR 337470 | Zbl 0992.03001

[7] J. Ferrante and C. Rackoff, A decision procedure for the first order theory of real addition with order. SIAM J. Comput. 4 (1975) 69-76. | MR 389572 | Zbl 0294.02022

[8] P. Ganty, R. Majumdar and B. Monmege, Bounded underapproximations. Form. Methods Syst. Des. 40 (2012) 206-231. | Zbl 1247.68140

[9] S. Ginsburg and E.H. Spanier, Semigroups, Presburger formulas and languages. Pacific J. Math. 16 (1966) 285-296. | MR 191770 | Zbl 0143.01602

[10] S. Ginsburg and E. Spanier, Finite-turn pushdown automata. SIAM J. Control Optim. 4 (1966) 429. | MR 204294 | Zbl 0147.25302

[11] S.A. Greibach, A note on undecidable properties of formal languages. Math. Syst. Theor. 2 (1968) 1-6. | MR 455542 | Zbl 0157.01902

[12] O.H. Ibarra, Reversal-bounded multicounter machines and their decision problems. J. ACM 25 (1978) 116-133. | MR 461988 | Zbl 0365.68059

[13] O.H. Ibarra and J. Su, A technique for proving decidability of containment and equivalence of linear constraint queries. J. Comput. Syst. Sci. 59 (1999) 1-28. | MR 1702938 | Zbl 0939.68028

[14] O.H. Ibarra, J. Su, Z. Dang, T. Bultan and R.A. Kemmerer, Counter machines and verification problems. Theor. Comput. Sci. 289 (2002) 165-189. | MR 1932894 | Zbl 1061.68095

[15] W. Karianto, Parikh automata with pushdown stack. Diploma thesis, RWTH Aachen (2004).

[16] F. Klaedtke and H. Rueß, Parikh automata and monadic second-order logics with linear cardinality constraints. Universität Freiburg, Tech. Rep. 177 (2002).

[17] F. Klaedtke and H. Rueß, Monadic second-order logics with cardinalities, in Proc. of ICALP. Lect. Notes Comput. Sci. 2719 (2003) 681-696. | MR 2080737 | Zbl 1039.03004

[18] S.Y. Kuroda, Classes of languages and linear bounded automata. Inform. Control 7 (1964) 207-223. | MR 169724 | Zbl 0199.04002

[19] M. Latteux, Mots infinis et langages commutatifs. RAIRO Inform. Théor. Appl. 12 (1978) 185-192. | Numdam | MR 510635 | Zbl 0387.68051

[20] D.R. Mazur, Combinatorics : A Guided Tour. Mathematical Association of Mathematics (2010). | MR 2572113 | Zbl 1187.05001

[21] P. Mckenzie, M. Thomas and H. Vollmer, Extensional uniformity for boolean circuits. SIAM J. Comput. 39 (2010) 3186-3206. | MR 2678071 | Zbl 1209.68254

[22] H. Seidl, T. Schwentick and A. Muscholl, Numerical document queries, in Principles of Database Systems. ACM, San Diego, CA, USA (2003) 155-166.

[23] H. Straubing, Finite Automata, Formal Logic, and Circuit Complexity. Birkhäuser, Boston (1994). | MR 1269544 | Zbl 0816.68086

[24] P. Tesson and D. Thérien, Logic meets algebra : the case of regular languages. Log. Meth. Comput. Sci. 3 (2007) 1-37. | MR 2295792 | Zbl 1128.03029

[25] L.P.D. Van Den Dries, Tame Topology and O-minimal Structures. Cambridge Univ. Press (1998). | MR 1633348 | Zbl 0953.03045

[26] P. Wolper and B. Boigelot, An automata-theoretic approach to Presburger arithmetic constraints, in Static Analysis (SAS'95). Lect. Notes Comput. Sci. 983 (1995) 21-32.

[27] S.D. Zilio and D. Lugiez, Xml schema, tree logic and sheaves automata, in Rewriting Techniques and Applications (2003) 246-263. | MR 2071589 | Zbl 1038.68039