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.
Mots-clés : automata, semilinear sets, affine functions, counter machines
@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}, pages = {511--545}, publisher = {EDP-Sciences}, volume = {46}, number = {4}, year = {2012}, doi = {10.1051/ita/2012013}, mrnumber = {3107862}, zbl = {1279.68136}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ita/2012013/} }
TY - JOUR AU - Cadilhac, Michaël AU - Finkel, Alain AU - McKenzie, Pierre TI - Affine Parikh automata JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2012 SP - 511 EP - 545 VL - 46 IS - 4 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita/2012013/ DO - 10.1051/ita/2012013 LA - en ID - ITA_2012__46_4_511_0 ER -
%0 Journal Article %A Cadilhac, Michaël %A Finkel, Alain %A McKenzie, Pierre %T Affine Parikh automata %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2012 %P 511-545 %V 46 %N 4 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita/2012013/ %R 10.1051/ita/2012013 %G en %F 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) no. 4, pp. 511-545. doi : 10.1051/ita/2012013. http://archive.numdam.org/articles/10.1051/ita/2012013/
[1] Reversal-bounded multipushdown machines. J. Comput. Syst. Sci. 8 (1974) 315-332. | MR | Zbl
and ,[2] Parikh-bounded languages, in ICALP. Lect. Notes Comput. Sci. 115 (1981) 316-323. | MR | Zbl
and ,[3] Reversal-bounded acceptors and intersections of linear languages. SIAM J. Comput. 3 (1974) 283. | MR | Zbl
, and ,[4] Analogies of PAL and COPY, in Fundamentals of Computation Theory. Lect. Notes in Comput. Sci. 117 (1981) 61-70. | MR | Zbl
,[5] One-reversal counter machines and multihead automata : revisited, in Proc. of SOFSEM. ACM (2011) 166-177. | MR | Zbl
, , , and ,[6] A Mathematical Introduction to Logic. Academic Press (1972). | MR | Zbl
,[7] A decision procedure for the first order theory of real addition with order. SIAM J. Comput. 4 (1975) 69-76. | MR | Zbl
and ,[8] Bounded underapproximations. Form. Methods Syst. Des. 40 (2012) 206-231. | Zbl
, and ,[9] Semigroups, Presburger formulas and languages. Pacific J. Math. 16 (1966) 285-296. | MR | Zbl
and ,[10] Finite-turn pushdown automata. SIAM J. Control Optim. 4 (1966) 429. | MR | Zbl
and ,[11] A note on undecidable properties of formal languages. Math. Syst. Theor. 2 (1968) 1-6. | Zbl
,[12] Reversal-bounded multicounter machines and their decision problems. J. ACM 25 (1978) 116-133. | MR | Zbl
,[13] A technique for proving decidability of containment and equivalence of linear constraint queries. J. Comput. Syst. Sci. 59 (1999) 1-28. | MR | Zbl
and ,[14] Counter machines and verification problems. Theor. Comput. Sci. 289 (2002) 165-189. | MR | Zbl
, , , and ,[15] Parikh automata with pushdown stack. Diploma thesis, RWTH Aachen (2004).
,[16] Parikh automata and monadic second-order logics with linear cardinality constraints. Universität Freiburg, Tech. Rep. 177 (2002).
and ,[17] Monadic second-order logics with cardinalities, in Proc. of ICALP. Lect. Notes Comput. Sci. 2719 (2003) 681-696. | MR | Zbl
and ,[18] Classes of languages and linear bounded automata. Inform. Control 7 (1964) 207-223. | MR | Zbl
,[19] Mots infinis et langages commutatifs. RAIRO Inform. Théor. Appl. 12 (1978) 185-192. | Numdam | MR | Zbl
,[20] Combinatorics : A Guided Tour. Mathematical Association of Mathematics (2010). | MR | Zbl
,[21] Extensional uniformity for boolean circuits. SIAM J. Comput. 39 (2010) 3186-3206. | MR | Zbl
, and ,[22] Numerical document queries, in Principles of Database Systems. ACM, San Diego, CA, USA (2003) 155-166.
, and ,[23] Finite Automata, Formal Logic, and Circuit Complexity. Birkhäuser, Boston (1994). | MR | Zbl
,[24] Logic meets algebra : the case of regular languages. Log. Meth. Comput. Sci. 3 (2007) 1-37. | MR | Zbl
and ,[25] Tame Topology and O-minimal Structures. Cambridge Univ. Press (1998). | MR | Zbl
,[26] An automata-theoretic approach to Presburger arithmetic constraints, in Static Analysis (SAS'95). Lect. Notes Comput. Sci. 983 (1995) 21-32.
and ,[27] Xml schema, tree logic and sheaves automata, in Rewriting Techniques and Applications (2003) 246-263. | MR | Zbl
and ,Cité par Sources :