Ist es entscheidbar, ob die Ausgangslänge eines Wandlers durch die Eingangslänge begrenzt ist?

Die hier betrachteten Wandler sind jene, die Wikipedia Finite-State-Wandler nennt . Das Verhalten eines Wandlers , dh die von ihm berechnete Beziehung, wird geschrieben : Ein Wort ist eine Ausgabe für iff . $T$ $[T]$ $y$ $x$ $x[T]y$

Frage: Ist das folgende Problem entscheidbar:

Gegeben: Ein Wandler und eine reguläre Sprache Entscheiden: Enthält es, dass , ein Wort, impliziert, dass ? $T$ $L$
$\forall x \in L$ $\forall y$ $x[T]y$ $|y| \leq |x|$

Ich suche nach nicht trivialen Analysen / lösbaren Unterfällen, Reduktion auf bekannte Probleme und / oder verwandte Referenzen. (im Moment nicht einmal sicher, ob es im Allgemeinen entscheidbar ist ...?)

Motivation: Dieses Problem wurde durch die Analyse / Untersuchung des automatisierten Theorems zum Nachweis zahlentheoretischer Probleme im Allgemeinen und einer hoch untersuchten, Collatz-Vermutung im Besonderen, inspiriert .

ds.algorithms reference-request automata-theory regular-language dfa vzn
quelle

ps (sollte bekannt sein, wie lange bekannt) FSM-Wandler sind leistungsfähig genug, um einzelne Iterationen von TM "Momentanbeschreibungen" zu berechnen . Daher scheint das Problem möglicherweise mit LBAs und CSLs zu zusammenhängen .

vzn

Von

Sie sprechen von der Anzahl der Ausgänge am Eingang

, oder? Nicht die Größe der Ausgänge, in diesem Fall wäre es ganz einfach.

| F (x) |

$|F(x)|$

x

$x$

Michaël Cadilhac

sind beide Wörter und

ist die Länge des "Ausgabe" -Wortes. Ich habe einige Ideen, sehe aber im Moment nichts Geradliniges, daher die Frage. Es ist vermutlich nicht trivial, z. B. aufgrund von

Ein- / Ausgängen bei einigen Übergängen usw.

x, F (x)

$x, F(x)$

| F (x) |

$|F(x)|$

ϵ

$\epsilon$

vzn

Sie nehmen also implizit an, dass Ihr Wandler funktionsfähig ist - notationstechnisch war mir das nicht klar :-) Was ist also mit Folgendem: Sei

ein (möglicherweise nicht deterministischer) Wandler und

eine bestimmte reguläre Sprache. Modifiziere

in einen Wandler

so dass er prüft, ob sein Eingang in

ist und alle seine Zustände erreichbar und gemeinsam erreichbar sind. Dann

für alle

wenn es im Wandler

keinen einfachen Zyklus gibt

T

$T$

L

$L$

T

$T$

T^{'}

$T'$

L

$L$

| T (w) | \leq | w |

$|T(w)| \leq |w|$

w \in L

$w \in L$

T^{'}

$T'$ für die die Eingabe kleiner als die Ausgabe ist und einige zusätzliche einfache Eigenschaften für die Übergänge, die in keinem SCC angezeigt werden.

Michaël Cadilhac

okay. für "Eingabe ist kleiner als Ausgabe" meinen Sie über den Zyklus? Ich denke, das ist es wert, als Antwort aufgeschrieben zu werden. Es gab eine andere Möglichkeit, dieses / verwandte Problem mit strengeren Kriterien zu formulieren, was vermutlich nicht (so) einfach ist. Vielleicht versuchen Sie es erneut ("Teil 2 / Fortsetzung / Follow-up"), wenn Ihre Antwort richtig erscheint. Dieses aktuelle Problem ist wahrscheinlich fast ein Sonderfall des umfassenderen Problems.

vzn

Der andere Mitwirkende hat seine Antwort gelöscht, vielleicht um mich meinen obigen Kommentar erweitern zu lassen, also hier ist es.

Sei ein möglicherweise nicht deterministischer Wandler und eine reguläre Sprache. Modifiziere in einen Wandler , der prüft, ob sein Eingang in (indem z. B. der in das kartesische Produkt der Zustandssätze von und Zustand geändert wird und die Übergangsfunktion so modifiziert wird, dass der Teil der Zustände ist wird ordnungsgemäß aktualisiert, wobei das Verhalten von beibehalten wird .) $T$ $L$ $T$ $T'$ $L$ $T$ $L$ $L$ $T$

$T'$ $\rho_1 C_1\rho_2 C_2 \cdots \rho_n C_n \rho_{n+1}$ $\rho_1\rho_2 \cdots \rho_{n+1}$ $T'$ $C_i$ $T'$ $\rho_i$ $\rho_{i+1}$

$\rho_1\rho_2\cdots\rho_{n+1}$
$i$ $C_i$

$\big[$ $x, y$ $x[T']y$ $|y| \leq |x|$ $\big]$

Der Beweis ist ziemlich unmittelbar. Da die letztere Eigenschaft entscheidbar ist (da die Anzahl der Zweige und auch die Anzahl der einfachen Zyklen begrenzt ist), zeigt dies, dass das Problem der Frage entscheidbar ist.

Michaël Cadilhac
quelle

L

$L$

n \geq 1

$n \geq 1$

S_{n}

$S_n$

k \geq 1

$k \geq 1$

L_{\leq n}^{S_{n}} = L_{\leq n + k}^{S_{n}}

$L^{S_n}_{\leq n} = L^{S_n}_{\leq n+k}$

@ EmilJeřábek In der Tat ist es ganz klar in Co-NL (daher in NL).

Michaël Cadilhac

@MarzioDeBiasi Danke! Ich habe Ihre Nachricht in der Tat nicht gesehen. Ich werde daran arbeiten, Ihre Zeit zurückzuerstatten, wenn ich welche habe.

Michaël Cadilhac

Ist es entscheidbar, ob die Ausgangslänge eines Wandlers durch die Eingangslänge begrenzt ist?

Antworten: