User:Parhamhoushmand/Parikh Automaton

A Parikh automaton.

In theoretical computer science , and in particular in automata theory , a Parikh automaton is a non-deterministic finite automaton whose transitions include vectors of natural integers which make it possible to test whether the sum of the vectors of a calculation satisfies a semi-linear constraint . The interest of this family of automata is that it has other equivalent characterizations, in the form of a Turing machine and in a more algebraic form, called RCM .

Informal description

A Parikh automaton is a finite automaton whose transitions are labeled by pairs, Oris a letter of the input alphabet andis a vector of, for an integer. A path is a sequence

$q_{0}\xrightarrow {a_{1},v_{1}} q_{1}\xrightarrow {a_{2},v_{2}} \cdots q_{n-1}\xrightarrow {a_{n},v_{n}} q_{n}$

of transitions which calculates the wordand the vector, where the sum is done component by component. The acceptance condition is given by a set of terminal states and a semi-linear set. A path is a successful calculation if, starting from the initial state, it reaches a final state and if its vector belongs to the given semi-linear set.

Parikh automata were introduced in 2003 in the study of second-order logic  . These automata accept the same formal languages ​​as Turing machines with reversal bounded counters  . This family in turn coincides with a class defined by Massazza under the name RCM  class .

Example

The automaton of introduction  , with the constraint, accepts all wordsabout the alphabetwhich begins and ends with a, and such that. `

Parikh Automata

Semi-linear set

A subset of $\mathbb {N} ^{d}$ is linear if it is of the form

$u_{0}+u_{1}\mathbb {N} +\cdots +u_{k}\mathbb {N} =\{u_{0}+t_{1}u_{1}+\ldots +t_{m}u_{m}\mid t_{1},\ldots ,t_{m}\in \mathbb {N} \}$

for vectors $u_{0},\ldots ,u_{m}$. It is therefore the set of linear combinations, with natural integer coefficients, of a finite set of vectors of

$\mathbb {N} ^{d}$, to which is added the vector $u_{0}$. For example, for $d=3$,$(1,0,0)+(1,1,1)\mathbb {N} =\{(n+1,n,n)|n\in \mathbb {N} \}$ is a very simple linear set.

Un sous-ensemble de $\mathbb {N} ^{d}$ est semi-linéaire s'il est une union finie de parties linéaires. Tout ensemble semi-linéaire possède une représentation inambigue, où les unions sont disjointes et où les écritures comme combinaisons linéaires sont uniques.

Définition des automates

Un automate de Parikh de dimension $d\geq 1$ est un tuple ${\mathcal {A}}=(\Sigma ,Q,q_{I},F,C,\Delta )$, où

• $\Sigma$ est l'alphabet,
• $Q$ est l'ensemble d'états
• $q_{I}\in Q$ est l'état initial
• $F\subset Q$ est l’ensemble des états terminaux
• $C\subset \mathbb {N} ^{d}$ est l'ensemble des contraintes semi-linéaires
• $\Delta \subset Q\times (\Sigma \times \mathbb {N} ^{d})\times Q$ est la relation de transition.

Un chemin dans l'automate est une suite

$q_{0}\xrightarrow {a_{1},v_{1}} q_{1}\xrightarrow {a_{2},v_{2}} \cdots q_{n-1}\xrightarrow {a_{n},v_{n}} q_{n}$

où, pour $1\leq i\leq n$, le triplet $(q_{i-1),(a_{i},v_{i}}q_{i})$ est dans $\Delta$. L'étiquette de ce chemin est le couple $(a_{1}\cdots a_{n},v_{1}+\cdots +v_{n})$. Le chemin est réussi ou acceptant si $q_{0}=q_{I}$, $q_{n}\in F$ et si de plus le vecteur $v_{1}+\cdots +v_{n}$ est dans $C$. Dans ce cas, le mot $w=a_{1}\cdots a_{n}$ est accepté ou reconnu par l'automate ${\cal {A}}$. Le langage reconnu par ${\cal {A}}$ est noté $L({\cal {A)}}$.

Automates inambigus

Un automate de Parikh faiblement inambigu pour les contraintes $n_{1}=n_{2}+n_{3}$ et $n_{2}<n_{3}$

Un automate de Parikh est faiblement inambigu si, pour tout mot, il existe au plus un chemin réussi. L'automate de la figure ci-contre est faiblement inambigu. Il a pour ensemble semi-linéaire de contraintes l'ensemble $C=\{(n_{1},n_{2},n_{3})\mid n_{1}=n_{2}+n_{3}{\text{ et }}n_{2}<n_{3}\}$. Si on oublie la partie semi-linéaire, l'automate sous-jacent, qui reconnait le langage $c^{*}(a+b)^{+}$, est en revanche un automate fini ambigu.

La famille des langages reconnus par des automates de Parikh faiblement inambigus est fermée par intersection ; la fermeture par union ou par complémentation est une question encore ouverte. Il existe des langages inhéremment faiblement inambigus au sens que tout automate de Parikh les reconnaissants est faiblement ambigu.

Caractérisation par machines de Turing

Une machine de Turing à $k$ compteurs est une machine de Turing qui possède, en plus de ses attributs usuels, un ensemble de $k$ compteurs. La machine, dans l'état $q$ et en lisant une lettre $a$ sur sa bande d'entrée, peut examiner ses compteurs, et incrémenter ou décrémenter certains de ses compteurs. La machine ne connaît pas la valeur de ses compteurs mais sait tester s'ils sont nuls ou non. Une machine de Turing est à renversements bornés (en anglais « reversal bounded ») si sa tête de lecture ne peut changer de direction qu'un nombre borné de fois ; plus précisément, elle est $(m,n)$-bornée si elle peut changer de direction au plus $m$ fois, et si chaque compteur ne peut alterner l'incrémentation et la décrémentation au plus $n$ fois. Une machine de Turing, à $k$ compteurs et $(m,n)$-bornée est inambigue si, de plus, chaque mot possède au plus un calcul acceptant.

Theorem—Les automates de Parikh reconnaissent les mêmes langages que les machines de Turing à compteurs et à renversements bornés · .

L'égalité de ces familles de langages n'est plus vraie dans le cas déterministe. En revanche, la version inambigue est valide :

Theorem—Les automates de Parikh faiblement inambigus reconnaissent les mêmes langages que les machines de Turing à compteurs et à renversements bornés inambigus.

Langages RCM

Paolo Massazza a introduit en 1993 une famille de langages appelée RCM. La construction rappelle, mais de loin, la représentation des langages algébriques par langages de Dyck. Ces langages sont définis comme suit.

On se donne un alphabet $A=\{a_{1},\ldots ,a_{d}\}$ totalement ordonné avec $a_{1}<\cdots <a_{d}$. À tout ensemble semi-linéaire $C$ de dimension $d$ on associe le langage $[C]=\{w\in A^{*}\mid (|w|_{a_{1}},\ldots ,|w|_{a_{d}})\in C\}$. Ce langage est l'ensemble des mots dont les nombres d'occurrences de chaque lettre satisfont les contraintes de $C$. Si par exemple $C_{0}=\{(n,m,n,m)|n,m\geq 0\}$ et l'alphabet est $a<b<c<d$, le langage $[C_{0}]$est l'ensemble de tous les mots sur ces 4 lettres qui ont autant d'occurrences de $a$ que de $c$ et autant de $b$ que de $d$.

Par définition, un langage $L$ sur un alphabet $\Sigma$ appartient à la famille RCM s'il existe un langage rationnel $R$ sur $A=\{a_{1},\ldots ,a_{d}\}$, un ensemble semi-linéaire $C\subset \mathbb {N} ^{d}$ et un morphisme préservant la longueur $\mu :A^{*}\to \Sigma ^{*}$ qui est injectif sur $R\cap [C]$ tels que

$L=\mu (R\cap [C])$.

Par exemple, le langage $L_{abab}=\{a^{n}b^{m}a^{n}b^{m}|n,m\geq 0\}$ est dans la famille RCM parce qu'il s'écrit sous la forme $L_{abab}=\mu (R\cap [C_{0}])$, où $C_{0}$ est l'ensemble semi-linaire défini ci-dessus et $\mu$ identifie $a$ et $c$ respectivement $b$ et $d$.

Le lien entre les langages RCM est les automates de Parikh est le résultat suivant :

Theorem—Les automates de Parikh faiblement inambigus reconnaissent exactement les langages de la famille RCM.

Bibliographie

• Alin Bostan; Arnaud Carayol; Florent Koechlin; Cyril Nicaud (2020). "Weakly-unambiguous Parikh automata and their link to holonomic series" (PDF). 47th International Colloquium on Automata, Languages, and Programming: 114:1-114:16. doi:10.4230/LIPIcs.ICALP.2020.114. B. Retrieved 28 mai 2020. {{cite journal}}: Check date values in: |access-date= (help)CS1 maint: unflagged free DOI (link).
• Michaël Cadilhac; Alain Finkel; Pierre McKenzie (2012). "Affine Parikh automata". RAIRO Theor. Inf. and Applic. 46 (4): 511-545. doi:10.1051/ita/2012013..
• Michaël Cadilhac; Alain Finkel; Pierre McKenzie (2013). "Unambiguous constrained automata". Int. J. Found. Comput. Sci. 24 (7): 1099-1116. doi:10.1142/S0129054113400339..
• Giusi Castiglione; Paolo Massazza (2017). "On a class of languages with holonomic generating functions". Theoretical Computer Science. 658: 74–84. doi:10.1016/j.tcs.2016.07.022..

• Thomas Colcombet, « Unambiguity in automata theory », dans Jeffrey Shallit et Alexander Okhotin, Descriptional Complexity of Formal Systems - 17th International Workshop, Springer, coll. « LectureNotes in Computer Science » (no 9118), 2015 (DOI 10.1007/978-3-319-19225-3_1), p. 3–18.

• Oscar H. Ibarra (1978). "Reversal-bounded multicounter machines and their decision problems". Journal of the ACM. 25 (1): 116-133. doi:10.1145/322047.322058..

• Felix Klaedtke et Harald Rueß, « Monadic second-order logics with cardinalities », dans Automata, Languages and Programming, 30th International Colloquium, Springer, coll. « LectureNotes in Computer Science » (no 2719), 2003 (DOI 10.1007/3-540-45061-0_54), p. 74–84.
• Paolo Massazza (1993). "Holonomic functions and their relation to linearly constrained languages". RAIRO - Informatique Théorique et Applications. 27 (2): 149-161. doi:10.1051/ita/1993270201491..

• Guha, Shibashis; Jecker, Ismaël; Lehtinen, Karoliina; Zimmermann, Martin (2022). "Parikh Automata over Infinite Words". Leibniz International Proceedings in Informatics (LIPIcs). 250. Schloss Dagstuhl – Leibniz-Zentrum für Informatik: 40:1–40:20. doi:10.4230/LIPIcs.FSTTCS.2022.40. ISBN 978-3-95977-261-7.{{cite journal}}: CS1 maint: unflagged free DOI (link)

• Erlich, Enzo; Guha, Shibashis; Jecker, Ismaël; Lehtinen, Karoliina (2022-09-16). "History-deterministic Parikh Automata". arXiv. arXiv:2209.07745.

Articles liés

• Automate fini
• Machine de Turing
• Théorème de Parikh

[[Category:Automata (computation)]]