Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-15T02:02:09.722Z 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.

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

The Parikh finite word automaton (PA) was introduced and studied in 2003 by Klaedtke andRueß. Natural variants of the PA arise from viewing a PA equivalently as an automaton thatkeeps a count of its transitions and semilinearly constrains their numbers. Here we adoptthis view and define the affine PA, that extends the PA by having eachtransition induce an affine transformation on the PA registers, and the PA onletters, that restricts the PA by forcing any two transitions on the sameletter to affect the registers equally. Then we report on the expressiveness, closure, anddecidability properties of such PA variants. We note that deterministic PA are strictlyweaker than deterministic reversal-bounded counter machines.

Keywords

Automatasemilinear setsaffine functionscounter machines

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.