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

Abstract

top
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.

How to cite

top

Cadilhac, Michaël, Finkel, Alain, and McKenzie, Pierre. "Affine Parikh automata∗." RAIRO - Theoretical Informatics and Applications 46.4 (2012): 511-545. <http://eudml.org/doc/277829>.

@article{Cadilhac2012,
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.},
author = {Cadilhac, Michaël, Finkel, Alain, McKenzie, Pierre},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Automata; semilinear sets; affine functions; counter machines; automata},
language = {eng},
month = {11},
number = {4},
pages = {511-545},
publisher = {EDP Sciences},
title = {Affine Parikh automata∗},
url = {http://eudml.org/doc/277829},
volume = {46},
year = {2012},
}

TY - JOUR
AU - Cadilhac, Michaël
AU - Finkel, Alain
AU - McKenzie, Pierre
TI - Affine Parikh automata∗
JO - RAIRO - Theoretical Informatics and Applications
DA - 2012/11//
PB - EDP Sciences
VL - 46
IS - 4
SP - 511
EP - 545
AB - 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.
LA - eng
KW - Automata; semilinear sets; affine functions; counter machines; automata
UR - http://eudml.org/doc/277829
ER -

References

top
  1. B.S. Baker and R.V. Book, Reversal-bounded multipushdown machines. J. Comput. Syst. Sci.8 (1974) 315–332.  Zbl0309.68043
  2. M. Blattner and M. Latteux, Parikh-bounded languages, in ICALP. Lect. Notes Comput. Sci.115 (1981) 316–323.  Zbl0462.68057
  3. R. Book, M. Nivat and M. Paterson, Reversal-bounded acceptors and intersections of linear languages. SIAM J. Comput.3 (1974) 283.  Zbl0276.68027
  4. F. Brandenburg, Analogies of PAL and COPY, in Fundamentals of Computation Theory. Lect. Notes in Comput. Sci.117 (1981) 61–70.  
  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.  Zbl1298.68127
  6. H.B. Enderton, A Mathematical Introduction to Logic. Academic Press (1972).  Zbl0298.02002
  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.  Zbl0294.02022
  8. P. Ganty, R. Majumdar and B. Monmege, Bounded underapproximations. Form. Methods Syst. Des.40 (2012) 206–231.  Zbl1247.68140
  9. S. Ginsburg and E.H. Spanier, Semigroups, Presburger formulas and languages. Pacific J. Math.16 (1966) 285–296.  Zbl0143.01602
  10. S. Ginsburg and E. Spanier, Finite-turn pushdown automata. SIAM J. Control Optim.4 (1966) 429.  Zbl0147.25302
  11. S.A. Greibach, A note on undecidable properties of formal languages. Math. Syst. Theor.2 (1968) 1–6.  Zbl0157.01902
  12. O.H. Ibarra, Reversal-bounded multicounter machines and their decision problems. J. ACM25 (1978) 116–133.  Zbl0365.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.  Zbl0939.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.  Zbl1061.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.  Zbl1039.03004
  18. S.Y. Kuroda, Classes of languages and linear bounded automata. Inform. Control7 (1964) 207–223.  Zbl0199.04002
  19. M. Latteux, Mots infinis et langages commutatifs. RAIRO Inform. Théor. Appl.12 (1978) 185–192.  Zbl0387.68051
  20. D.R. Mazur, Combinatorics : A Guided Tour. Mathematical Association of Mathematics (2010).  Zbl1187.05001
  21. P. McKenzie, M. Thomas and H. Vollmer, Extensional uniformity for boolean circuits. SIAM J. Comput.39 (2010) 3186–3206.  Zbl1209.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).  Zbl0816.68086
  24. P. Tesson and D. Thérien, Logic meets algebra : the case of regular languages. Log. Meth. Comput. Sci.3 (2007) 1–37.  Zbl1128.03029
  25. L.P.D. van den Dries, Tame Topology and O-minimal Structures. Cambridge Univ. Press (1998).  
  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.  Zbl1038.68039

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.