Automates reconnaissant pour un code fini

Soit un alphabet fini. Un code sur est un sous - ensemble de de telle sorte que chaque mot dans peut être unique représenté sous la forme d' une concaténation de mots . Un code est fini siest fini. Que sait-on des automates (minimaux) reconnaissant pour un code fini ? Existe-t-il une caractérisation de tels automates (en termes de structure de l'automate, sans connaître )? Est-il possible, avec un tel automate, d'extraire le code en temps polynomial? $\Sigma$ $X$ $\Sigma$ $\Sigma^*$ $X^*$ $X$ $X$ $|X|$ $X^*$ $X$ $X$ $X$

Je m'intéresse également à ces questions lorsque nous omettons le fait que est un code, c'est-à-dire supposons seulement que est un ensemble fini de mots. $X$ $X$

automata-theory Andrew Ryzhikov
la source

Que voulez-vous savoir sur ces automates? Il semble qu'il soit facile de construire un DFA pour dont la taille peut être facilement caractérisée (c'est fondamentalement le nombre de préfixes uniques de chaînes dans , et est donc tout au plus la somme des longueurs de mots dans ; en particulier , c'est la taille polynomiale). Étant donné un tel DFA, il semble également facile d'extraire les mots de code dans en énumérant tous les cycles du nœud de départ vers lui-même. Quelles sont précisément vos questions? Quelle réflexion avez-vous déjà faite? Consultez la partie «Les questions doivent être basées sur ...» de notre centre d'aide .

X^{*}

$X^*$

X

$X$

X

$X$

X

$X$

@DW, évidemment, tous les automates n'ont pas cette propriété. Je demande donc s'il y a une caractérisation (espérons-le, polynomiale) de ces automates. De plus, je ne vois pas comment extraire en énumérant tous les cycles de l'état initial à lui-même. En fait, il peut y avoir un nombre infini de cycles, car nous ne pouvons pas nous limiter uniquement aux cycles sans auto-intersections. Pouvez-vous être plus précis?

X

$X$

Andrew Ryzhikov

Si je comprends bien, vous avez posé une question sur les automates minimaux. Je pense que tous les DFA minimaux seront isomorphes à celui que j'ai décrit. Si vous posez des questions sur tous les automates, pas nécessairement minimes, je vous suggère de modifier la question pour clarifier. Je ne comprends pas pourquoi vous ne pouvez pas vous limiter uniquement aux cycles sans auto-intersections; la propriété sans préfixe signifie qu'il est sûr de le faire, et si est fini, il n'y aura qu'un nombre fini de tels cycles. Je vous suggère de réfléchir au problème pendant un certain temps, puis de modifier la question pour partager tous les résultats que vous avez pu obtenir jusqu'à présent.

X

$X$

Cette question n'est-elle pas la même que la première version de cstheory.stackexchange.com/questions/4284/… , où

pourraient différer, sauf que vous demandez également le temps d'exécution?

K

$K$

K^{'}

$K'$

domotorp

@domotorp Vous avez raison, vérifier si un ensemble de mots est un code peut être fait en temps polynomial, et c'est un fait assez connu (voir ex. www-igm.univ-mlv.fr/~berstel/LivreCodes/ Codes.html , sous-section 0.4). Ce que je veux, c'est d'avoir seulement un automate minimal reconnaissant quelque chose, vérifiez si ce quelque chose est une star de code.

Andrew Ryzhikov

Réponses:

Étant donné que cette question n'a reçu aucune réponse pendant longtemps, permettez-moi de répondre partiellement à la première partie de la question:

Que sait-on des automates (minimaux) reconnaissant pour un code fini ? $X^∗$ $X$

Étant donné un ensemble fini de mots , l' automate fleur de est l'automate non déterministe fini , où , $X$ $X^*$ $\mathcal{A} = (Q, A, E, I, F)$ $Q = \{1, 1\} \cup \{ (u, v) \in A^+ \times A^+ \mid uv \in X \}$ , avec quatre types de transitions: $I = F = \{(1,1)\}$ Il est facile de voir que cet automate reconnaît. Par exemple, siet, l'automate fleur deest le suivant

\begin{aligned} (u, une v) & \overset{une}{⟶} (u une, v) tel que u une v \in X, (u, v) \neq (1, 1) \\ (u, une) & \overset{une}{⟶} (1, 1) tel que u une \in X, u \neq 1 \\ (1, 1) & \overset{une}{⟶} (une, v) tel que une v \in X, v \neq 1 \\ (1, 1) & \overset{une}{⟶} (1, 1) tel que une \in X} \end{aligned}

$\begin{align*} (u, av) &\enspace{\buildrel{a} \over\longrightarrow}\enspace (ua, v) \text{ such that } uav \in X,\ (u, v) \neq (1,1) \\ (u, a) &\enspace{\buildrel{a} \over\longrightarrow}\enspace (1, 1) \text{ such that } ua \in X,\ u \neq 1 \\ (1, 1) &\enspace{\buildrel{a} \over\longrightarrow}\enspace(a, v) \text{ such that } av \in X,\ v \neq 1\\ (1, 1) &\enspace{\buildrel{a} \over\longrightarrow}\enspace (1, 1) \text{ such that } a \in X \bigr\} \end{align*}$

X^{*}

$X^*$

A = {a, b}

$A= \{a, b\}$

X = {a, b a, a a b, a b a}

$X = \{a, ba, aab, aba\}$

X^{*}

$X^*$

$\qquad\qquad\qquad$

Rappelons qu'un automate n'est pas ambigu si, étant donné deux états et et un mot , il y a au plus un chemin de à avec l'étiquette . Ensuite, le résultat suivant est valable: $p$ $q$ $w$ $p$ $q$ $w$

Théorème [1, Thm 4.2.2]. L'ensemble est un code si l'automate fleur de est sans ambiguïté. $X$ $X^*$

L'automate fleur a également une propriété algébrique qui le rend relativement proche de l'automate minimal. Cette propriété est valable pour tout ensemble fini , mais est plus facile à énoncer en se débarrassant du mot vide, c'est-à-dire en considérant un langage comme un sous-ensemble de au lieu de . $X$ $A^+$ $A^*$

Rappelons qu'un semi-groupe fini est localement trivial si, pour tout idempotent , . Un morphisme est localement trivial si pour tout idempotent dans , le semi-groupe est localement trivial. $R$ $e \in R$ $eRe = \{e\}$ $\pi:R \to S$ $e$ $S$ $\pi^{-1}(e)$

$T$ $X^+$ $X^+$ $T$ $L^+$ $\pi$ $T$ $S$ $X^+$

$\pi:T \to S$

$\mathcal{J}$

Références

[ 1 ] J. Berstel, D. Perrin, C. Reutenauer, Codes et automates . Encyclopedia of Mathematics and its Applications, 129. Cambridge University Press, Cambridge, 2010. xiv + 619 pp. ISBN: 978-0-521-88831-8

J.-E. Épingle
la source