Hostname: page-component-8448b6f56d-dnltx Total loading time: 0 Render date: 2024-04-18T06:43:38.326Z Has data issue: false hasContentIssue false
  • English
  • Français

Affine Parikh automata∗

Published online by Cambridge University Press:  02 August 2012

Michaël Cadilhac ,
Alain Finkel  and
Pierre McKenzie
Michaël Cadilhac
Affiliation:
DIRO, Université de Montréal, CP 6128 succ. centre-ville, Montréal QC, H3C 3J7, Canada. cadilhac@iro.umontreal.ca, mckenzie@iro.umontreal.ca. The third author is supported by the Natural Sciences and Engineering Research Council of Canada.
Alain Finkel
Affiliation:
LSV, ENS Cachan, CNRS, 61, avenue du Président Wilson, 94235 Cachan Cedex, France; finkel@lsv.ens-cachan.fr Ce travail a bénéficié d’une aide de l’Agence Nationale de la Recherche portant la référence “REACHARD-ANR-11-BS02-001”
Pierre McKenzie
Affiliation:
DIRO, Université de Montréal, CP 6128 succ. centre-ville, Montréal QC, H3C 3J7, Canada. cadilhac@iro.umontreal.ca, mckenzie@iro.umontreal.ca. The third author is supported by the Natural Sciences and Engineering Research Council of Canada.
Get access

Abstract

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.

Keywords

Automatasemilinear setsaffine functionscounter machines
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 46 , Issue 4: Special Issue: Non-Classical Models of Automata and Applications III (NCMA-2011) , October 2012 , pp. 511 - 545
Copyright
© EDP Sciences 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Baker, B.S. and Book, R.V., Reversal-bounded multipushdown machines. J. Comput. Syst. Sci. 8 (1974) 315–332. Google Scholar
Blattner, M. and Latteux, M., Parikh-bounded languages, in ICALP. Lect. Notes Comput. Sci. 115 (1981) 316–323. Google Scholar
Book, R., Nivat, M. and Paterson, M., Reversal-bounded acceptors and intersections of linear languages. SIAM J. Comput. 3 (1974) 283. Google Scholar
Brandenburg, F., Analogies of PAL and COPY, in Fundamentals of Computation Theory. Lect. Notes in Comput. Sci. 117 (1981) 61–70. Google Scholar
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.
H.B. Enderton, A Mathematical Introduction to Logic. Academic Press (1972).
Ferrante, J. and Rackoff, C., A decision procedure for the first order theory of real addition with order. SIAM J. Comput. 4 (1975) 69–76. Google Scholar
Ganty, P., Majumdar, R. and Monmege, B., Bounded underapproximations. Form. Methods Syst. Des. 40 (2012) 206–231. Google Scholar
Ginsburg, S. and Spanier, E.H., Semigroups, Presburger formulas and languages. Pacific J. Math. 16 (1966) 285–296. Google Scholar
Ginsburg, S. and Spanier, E., Finite-turn pushdown automata. SIAM J. Control Optim. 4 (1966) 429. Google Scholar
Greibach, S.A., A note on undecidable properties of formal languages. Math. Syst. Theor. 2 (1968) 1–6. Google Scholar
Ibarra, O.H., Reversal-bounded multicounter machines and their decision problems. J. ACM 25 (1978) 116–133. Google Scholar
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–28. Google Scholar
Ibarra, O.H., Su, J., Dang, Z., Bultan, T. and Kemmerer, R.A., Counter machines and verification problems. Theor. Comput. Sci. 289 (2002) 165–189. Google Scholar
W. Karianto, Parikh automata with pushdown stack. Diploma thesis, RWTH Aachen (2004).
F. Klaedtke and H. Rueß, Parikh automata and monadic second-order logics with linear cardinality constraints. Universität Freiburg, Tech. Rep. 177 (2002).
Klaedtke, F. and Rueß, H., Monadic second-order logics with cardinalities, in Proc. of ICALP. Lect. Notes Comput. Sci. 2719 (2003) 681–696. Google Scholar
Kuroda, S.Y., Classes of languages and linear bounded automata. Inform. Control 7 (1964) 207–223. Google Scholar
Latteux, M., Mots infinis et langages commutatifs. RAIRO Inform. Théor. Appl. 12 (1978) 185–192. Google Scholar
D.R. Mazur, Combinatorics : A Guided Tour. Mathematical Association of Mathematics (2010).
McKenzie, P., Thomas, M. and Vollmer, H., Extensional uniformity for boolean circuits. SIAM J. Comput. 39 (2010) 3186–3206. Google Scholar
H. Seidl, T. Schwentick and A. Muscholl, Numerical document queries, in Principles of Database Systems. ACM, San Diego, CA, USA (2003) 155–166.
H. Straubing, Finite Automata, Formal Logic, and Circuit Complexity. Birkhäuser, Boston (1994).
Tesson, P. and Thérien, D., Logic meets algebra : the case of regular languages. Log. Meth. Comput. Sci. 3 (2007) 1–37. Google Scholar
L.P.D. van den Dries, Tame Topology and O-minimal Structures. Cambridge Univ. Press (1998).
Wolper, P. and Boigelot, B., An automata-theoretic approach to Presburger arithmetic constraints, in Static Analysis (SAS’95). Lect. Notes Comput. Sci. 983 (1995) 21–32. Google Scholar
S.D. Zilio and D. Lugiez, Xml schema, tree logic and sheaves automata, in Rewriting Techniques and Applications (2003) 246–263.