Automaten, die

Sei ein endliches Alphabet. Ein Code über ist eine Teilmenge von , so dass jedes Wort in eindeutig als eine Verkettung von Worten dargestellt werden , in . Ein Code ist endlich, wenn ist endlich. Was ist über (minimale) Automaten bekannt, die für einen endlichen Code ? Gibt es eine Charakterisierung solcher Automaten (in Bezug auf die Struktur des Automaten, ohne )? Ist es möglich, mit einem solchen Automaten den Code extrahieren? $\Sigma$ $X$ $\Sigma$ $\Sigma^*$ $X^*$ $X$ $X$ $|X|$ $X^*$ $X$ $X$ $X$ in Polynomzeit?

Diese Fragen interessieren mich auch, wenn wir die Tatsache weglassen, dass ein Code ist, dh nur annehmen, dass eine endliche Menge von Wörtern ist. $X$ $X$

automata-theory Andrew Ryzhikov
quelle

Was möchten Sie über solche Automaten wissen? Es scheint einfach zu sein, einen DFA für

erstellen, dessen Größe leicht charakterisiert werden kann (es ist im Grunde die Anzahl der eindeutigen Präfixe von Zeichenfolgen in

und somit höchstens die Summe der Wortlängen in

, insbesondere es ist Polynomgröße). Angesichts eines solchen DFA scheint es auch einfach zu sein, die Codewörter in

zu extrahieren, indem alle Zyklen vom Startknoten zurück zu sich selbst aufgelistet werden. Was genau sind Ihre Fragen? Was hast du schon gedacht? Weitere Informationen finden Sie im Abschnitt "Fragen sollten auf ... basieren" in unserer Hilfe .

X^{*}

$X^*$

X

$X$

X

$X$

X

$X$

@ DW, natürlich haben nicht alle Automaten diese Eigenschaft. Ich frage also, ob es eine (hoffentlich polynomielle) Charakterisierung solcher Automaten gibt. Außerdem sehe ich nicht, wie man

extrahiert, indem man alle Zyklen vom Anfangszustand bis zu sich selbst auflistet. Tatsächlich kann es unendlich viele Zyklen geben, da wir uns nicht nur auf Zyklen ohne Selbstüberschneidungen beschränken können. Können Sie bitte genauer sein?

X

$X$

Andrew Ryzhikov

Wenn ich das richtig verstehe, haben Sie nach minimalen Automaten gefragt. Ich denke, alle minimalen DFAs werden isomorph zu dem sein, den ich beschrieben habe. Wenn Sie nach allen Automaten fragen, die nicht unbedingt minimal sind, empfehle ich Ihnen, die Frage zur Klärung zu bearbeiten. Ich verstehe nicht, warum Sie sich nicht nur auf Zyklen ohne Selbstüberschneidungen beschränken können. Die Eigenschaft ohne Präfix bedeutet, dass dies sicher ist. Wenn

endlich ist, gibt es nur endlich viele solcher Zyklen. Ich schlage vor, dass Sie eine Weile über das Problem nachdenken und dann die Frage bearbeiten, um alle Ergebnisse zu teilen, die Sie bisher erzielen konnten.

X

$X$

Ist diese Frage nicht dieselbe wie die erste Version von cstheory.stackexchange.com/questions/4284/… , in der

und

unterschiedlich sein können, außer dass Sie auch nach der Laufzeit fragen?

K

$K$

K^{'}

$K'$

Domotorp

@domotorp Sie haben Recht, zu prüfen, ob eine Reihe von Wörtern ein Code ist, kann in Polynomzeit durchgeführt werden, und dies ist eine recht bekannte Tatsache (siehe z. B. www-igm.univ-mlv.fr/~berstel/LivreCodes/). Codes.html , Unterabschnitt 0.4). Ich möchte, dass nur ein minimaler Automat etwas erkennt und prüft, ob dies ein Stern eines Codes ist.

Andrew

Da diese Frage lange Zeit keine Antwort erhalten hat, möchte ich eine teilweise Antwort auf den ersten Teil der Frage geben:

Was ist über (minimale) Automaten bekannt, die für einen endlichen Code ? $X^∗$ $X$

$X$ $X^*$ $\mathcal{A} = (Q, A, E, I, F)$ $Q = \{1, 1\} \cup \{ (u, v) \in A^+ \times A^+ \mid uv \in X \}$ $I = F = \{(1,1)\}$

\begin{aligned} (u, a v) & \overset{a}{⟶} (u a, v) such that u a v \in X, (u, v) \neq (1, 1) \\ (u, a) & \overset{a}{⟶} (1, 1) such that u a \in X, u \neq 1 \\ (1, 1) & \overset{a}{⟶} (a, v) such that a v \in X, v \neq 1 \\ (1, 1) & \overset{a}{⟶} (1, 1) such that a \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$

$p$ $q$ $w$ $p$ $q$ $w$

$X$ $X^*$

$X$ $A^+$ $A^*$

$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}$

Verweise

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

J.-E. Stift
quelle

Automaten, die

Antworten: