Affine Parikh automata∗
Michaël Cadilhac; Alain Finkel; Pierre McKenzie
RAIRO - Theoretical Informatics and Applications (2012)
- Volume: 46, Issue: 4, page 511-545
- ISSN: 0988-3754
Access Full Article
topAbstract
topHow to cite
topReferences
top- B.S. Baker and R.V. Book, Reversal-bounded multipushdown machines. J. Comput. Syst. Sci.8 (1974) 315–332.
- M. Blattner and M. Latteux, Parikh-bounded languages, in ICALP. Lect. Notes Comput. Sci.115 (1981) 316–323.
- R. Book, M. Nivat and M. Paterson, Reversal-bounded acceptors and intersections of linear languages. SIAM J. Comput.3 (1974) 283.
- F. Brandenburg, Analogies of PAL and COPY, in Fundamentals of Computation Theory. Lect. Notes in Comput. Sci.117 (1981) 61–70.
- 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).
- 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.
- P. Ganty, R. Majumdar and B. Monmege, Bounded underapproximations. Form. Methods Syst. Des.40 (2012) 206–231.
- S. Ginsburg and E.H. Spanier, Semigroups, Presburger formulas and languages. Pacific J. Math.16 (1966) 285–296.
- S. Ginsburg and E. Spanier, Finite-turn pushdown automata. SIAM J. Control Optim.4 (1966) 429.
- S.A. Greibach, A note on undecidable properties of formal languages. Math. Syst. Theor.2 (1968) 1–6.
- O.H. Ibarra, Reversal-bounded multicounter machines and their decision problems. J. ACM25 (1978) 116–133.
- 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.
- 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.
- 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).
- F. Klaedtke and H. Rueß, Monadic second-order logics with cardinalities, in Proc. of ICALP. Lect. Notes Comput. Sci.2719 (2003) 681–696.
- S.Y. Kuroda, Classes of languages and linear bounded automata. Inform. Control7 (1964) 207–223.
- M. Latteux, Mots infinis et langages commutatifs. RAIRO Inform. Théor. Appl.12 (1978) 185–192.
- D.R. Mazur, Combinatorics : A Guided Tour. Mathematical Association of Mathematics (2010).
- P. McKenzie, M. Thomas and H. Vollmer, Extensional uniformity for boolean circuits. SIAM J. Comput.39 (2010) 3186–3206.
- 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).
- P. Tesson and D. Thérien, Logic meets algebra : the case of regular languages. Log. Meth. Comput. Sci.3 (2007) 1–37.
- L.P.D. van den Dries, Tame Topology and O-minimal Structures. Cambridge Univ. Press (1998).
- 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.
- S.D. Zilio and D. Lugiez, Xml schema, tree logic and sheaves automata, in Rewriting Techniques and Applications (2003) 246–263.