nach oben

Theory of Computing Systems

Erschienen in:

07.11.2017

The Algebraic Theory of Parikh Automata

verfasst von: Michaël Cadilhac, Andreas Krebs, Pierre McKenzie

Erschienen in: Theory of Computing Systems | Ausgabe 5/2018

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The Parikh automaton model equips a finite automaton with integer registers and imposes a semilinear constraint on the set of their final settings. Here the theories of typed monoids and of rational series are used to characterize the language classes that arise algebraically. Complexity bounds are derived, such as containment of the unambiguous Parikh automata languages in NC¹. Affine Parikh automata, where each transition applies an affine transformation on the registers, are also considered. Relying on these characterizations, the landscape of relationships and closure properties of the classes at hand is completed, in particular over unary languages.

Vorheriger Artikel Collaborative Exploration of Trees by Energy-Constrained Mobile Robots

Nächster Artikel On Effective Birkhoff’s Ergodic Theorem for Computable Actions of Amenable Groups

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

The restriction that N is finite is needed to preserve the property that the monoids at hand are finitely generated. It is possible to define a sensible product of two infinite typed monoids, see [25]. We will however only need this particular case.

A full trio or cone is a class of languages closed under morphisms, inverse morphisms,and intersection with the regular languages.

A wreath product with an infinite typed monoid on the right results in an uncountablemonoid, an undesirable property that was circumvented in [25]. We note that Theorem 4stays true with a definition of wreath product mimicking that of [25].

A language L is bounded if L ⊆ w1∗w2∗⋯w k∗ for some words w ₁,w ₂,…,w _k.

Abdulla, P.A., Atig, M.F., Meyer, R., Salehi, M.S.: What’s Decidable about Availability Languages. In: FSTTCS, LIPIcs, vol. 45, pp. 192–205. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2015). https://doi.org/10.4230/LIPIcs.FSTTCS.2015.192

Akshay, S., Genest, B., Karelovic, B., Vyas, N.: On Regularity of Unary Probabilistic Automata. In: STACS, LIPIcs, vol. 47, pp. 8:1–8:14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik (2016). https://doi.org/10.4230/LIPIcs.STACS.2016.8

Barrington, D.A.M.: Bounded-width polynomial size branching programs recognize exactly those languages in NC¹. J. Comput. Syst. Sci. 38, 150–164 (1989)CrossRefMATH

Barrington, D.A.M., Thérien, D.: Finite monoids and the fine structure of NC¹. J. Assoc. Comput. Mach. 35, 941–952 (1988)MathSciNetCrossRefMATH

Behle, C., Krebs, A., Mercer, M.: Linear Circuits, Two-Variable Logic and Weakly Blocked Monoids. In: Mathematical Foundations of Computer Science, LNCS, vol. 4708, pp. 147–158. Springer, Berlin (2007)

Behle, C., Krebs, A., Reifferscheid, S.: Typed Monoids - an Eilenberg-Like Theorem for Non Regular Languages. In: Algebraic Informatics, LNCS, vol. 6742, pp. 97–114. Springer, Berlin (2011)

Berstel, J., Reutenauer, C.: Noncommutative Rational Series with Applications. Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge (2010)CrossRefMATH

Bu̇chi, J. R.: Weak second order arithmetic and finite automata. Z. Math. Logik Grundlagen Math. 6, 66–92 (1960)MathSciNetCrossRef

Cadilhac, M., Finkel, A., McKenzie, P.: Affine Parikh automata. RAIRO - Theoretical Informatics and Applications 46(04), 511–545 (2012). https://doi.org/10.1051/ita/2012013 MathSciNetCrossRefMATH

10.

Cadilhac, M., Finkel, A., McKenzie, P.: Bounded Parikh automata. Int. J. Found. Comput. Sci. 23(08), 1691–1709 (2012)MathSciNetCrossRefMATH

11.

Cadilhac, M., Finkel, A., McKenzie, P.: Unambiguous constrained automata. Int. J. Found. Comput. Sci. 24(7), 1099–1116 (2013). https://doi.org/10.1142/S0129054113400339 MathSciNetCrossRefMATH

12.

Caussinus, H., McKenzie, P., Thérien, D., Vollmer, H.: Nondeterministic NC¹ computation. J. Comput. Syst. Sci. 57, 200–212 (1998)CrossRefMATH

13.

Chomsky, N., Schützenberger, M.P.: The Algebraic Theory of Context-Free Languages. In: Computer Programming and Formal Systems, Studies in Logic and the Foundations of Mathematics, vol. 26, pp. 118–161. Elsevier, Amsterdam (1959). https://doi.org/10.1016/S0049-237X(09)70104-1

14.

Eilenberg, S.: Automata, Languages, and Machines, Volume B. Pure and Applied Mathematics. Academic Press, Cambridge (1976)

15.

Enderton, H.B.: A mathematical introduction to logic. Academic Press, Cambridge (1972)MATH

16.

Figueira, D., Libkin, L.: Path Logics for Querying Graphs: combining Expressiveness and Efficiency. In: LICS, pp. 329–340 (2015). https://doi.org/10.1109/LICS.2015.39

17.

Ginsburg, S., Spanier, E.H.: Bounded regular sets. Proc. Am. Math. Soc. 17(5), 1043–1049 (1966). https://doi.org/10.2307/2036087 MathSciNetCrossRefMATH

18.

Ginsburg, S., Spanier, E.H.: Semigroups, Presburger formulas and languages. Pac. J. Math. 16(2), 285–296 (1966)MathSciNetCrossRefMATH

19.

Hoenicke, J., Meyer, R., Olderog, E.R.: Kleene, Rabin, and Scott are Available. In: Proceedings of the 21St International Conference on Concurrency Theory, CONCUR’10, pp. 462–477. Springer, Berlin (2010)

20.

Ibarra, O.H.: Reversal-bounded multicounter machines and their decision problems. J. ACM 25(1), 116–133 (1978). https://doi.org/10.1145/322047.322058 MathSciNetCrossRefMATH

21.

Kambites, M.: Formal languages and groups as memory. Commun. Algebra 37(1), 193–208 (2009). https://doi.org/10.1080/00927870802243580 MathSciNetCrossRefMATH

22.

Karianto, W.: Parikh automata with pushdown stack. Diploma thesis RWTH Aachen (2004)

23.

Klaedtke, F., Rueß, H.: Monadic second-order logics with cardinalities. In: International Colloquium on Automata, Languages and Programming, LNCS, vol. 2719, pp. 681–696. Springer, Berlin (2003). https://doi.org/10.1007/3-540-45061-0_54

24.

Krebs, A.: Typed Semigroups, Majority Logic, and Threshold Circuits. Ph.D. thesis, Eberhard Karls University of Tübingen (2008)

25.

Krebs, A., Lange, K.J., Reifferscheid, S.: Characterizing TC⁰ in terms of infinite groups. Theory of Computing Systems 40(4), 303–325 (2007)MathSciNetCrossRefMATH

26.

Parikh, R.J.: On context-free languages. J. ACM 13(4), 570–581 (1966). https://doi.org/10.1145/321356.321364 CrossRefMATH

27.

Pin, J.E.: Mathematical foundations of automata theory (2016). https://www.irif.fr/~jep/PDF/MPRI/MPRI.pdf

28.

Salomaa, A., Soittola, M.: Automata-Theoretic Aspects of Formal Power Series. Springer, New York (1978)CrossRefMATH

29.

Straubing, H.: Finite Automata, Formal Logic, and Circuit Complexity. Birkäuser, Boston 1994. https://doi.org/10.1007/978-1-4612-0289-9

30.

Turakainen, P.: Some closure properties of the family of stochastic languages. Inf. Control. 18(3), 253–256 (1971)MathSciNetCrossRefMATH

31.

Vollmer, H.: Introduction to circuit complexity. Springer, Berlin (1999)CrossRefMATH

32.

Zare, D.: For a linear recurrence sequence (u _n)_n≥ 0, can {i|u _i > 0} be the set of Fibonacci numbers? MathOverflow (2015). http://mathoverflow.net/q/222379

Titel: The Algebraic Theory of Parikh Automata
verfasst von: Michaël Cadilhac
Andreas Krebs
Pierre McKenzie
Publikationsdatum: 07.11.2017
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 5/2018
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-017-9817-2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 5/2018

A Closer Look at Fault Tolerance

Exploration of the T-Interval-Connected Dynamic Graphs: the Case of the Ring

Self-Stabilizing Leader Election in Dynamic Networks

Co-c.e. Sets with Disconnected Complements

Publisher Correction: Editor’s Note

Exact Localisations of Feedback Sets