Czy jest rozstrzygalne, czy długość wyjściowa przetwornika jest ograniczona długością wejściową?

Rozważane tutaj przetworniki to te, które Wikipedia nazywa przetwornikami skończonymi . Zachowanie przetwornika , czyli relacja, którą oblicza, jest zapisywane : słowo jest wyjściem dla iff . $T$ $[T]$ $y$ $x$ $x[T]y$

Pytanie: Czy można rozstrzygnąć następujący problem:

Biorąc pod uwagę: Przetwornik i zwykły język Zdecyduj: Czy utrzymuje, że , słowo, oznacza, że? $T$ $L$
$\forall x \in L$ $\forall y$ $x[T]y$ $|y| \leq |x|$

Szukam nietrywialnych analiz / możliwych do rozwiązania podgrup, redukcji znanych problemów i / lub powiązanych odnośników. (w tej chwili nie jesteś nawet pewien, czy jest to w ogóle rozstrzygalne ...?)

Motywacja: problem ten został zainspirowany analizą / dociekaniem dotyczącym zautomatyzowanego twierdzenia dowodzącego wielu problemów teoretycznych w ogóle, a także wysoce zbadanego , w szczególności hipoteza Collatza .

— vzn
źródło

ps (powinienem wspomnieć, jak długo wiadomo) przetworniki FSM są wystarczająco mocne, aby obliczać pojedyncze iteracje TM „opisów natychmiastowych” . Stąd problem wydaje się być może odnosić się do LBAS i CSLs .

— vzn

Przezmówisz o liczbie wyjść na wejściu , prawda? Nie wielkość wyjść, w takim przypadku byłoby to dość proste.

| F (x) |

$|F(x)|$

x

$x$

— Michaël Cadilhac

x, F (x)

$x, F(x)$ to oba słowa, ajest długością słowa „wyjściowego”. mam jakieś pomysły, ale w tej chwili nie widzę niczego od razu, stąd pytanie. jest przypuszczalnie nietrywialny ze względu np. na wejścia / wyjścia na niektórych przejściach itp.

| F (x) |

$|F(x)|$

ϵ

$\epsilon$

— dniu

Więc domyślnie zakładasz, że twój przetwornik jest funkcjonalny - pod względem notacji, nie było dla mnie jasne :-) Co z następującymi kwestiami: Niech będzie (prawdopodobnie niedeterministycznym) przetwornikiem, a będzie danym językiem regularnym. Zmodyfikuj w przetwornik aby sprawdził, czy jego wejście jest w , a wszystkie jego stany są osiągalne i współosiągalne. Następniedla wszystkich iff nie ma prostego cyklu w przetworniku dla którego wejście jest mniejsze niż wyjście, a niektóre dodatkowe łatwe właściwości na przejściach nie pojawiają się w żadnym SCC.

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

— Michaël Cadilhac

ok. dla „wejście jest mniejsze niż wyjście” masz na myśli w całym cyklu? myślę, że warto to zapisać jako odpowiedź. istniał inny sposób sformułowania tego / powiązanego problemu za pomocą bardziej rygorystycznych kryteriów, który prawdopodobnie nie jest (jak) łatwy, może spróbuje ponownie na tym („część 2 / kontynuacja / kontynuacja”), jeśli twoja odpowiedź wydaje się poprawna. ten obecny problem jest prawdopodobnie prawie szczególnym przypadkiem szerszego problemu.

— vzn

Drugi współpracownik usunął swoją odpowiedź, być może, aby pozwolić mi rozszerzyć powyższy komentarz, więc oto jest.

Niech będzie prawdopodobnie niedeterministycznym przetwornikiem, a będzie zwykłym językiem. Zmodyfikuj w przetwornik który sprawdza, czy jego wejście jest w (np. Zmieniając zestaw stanów na iloczyn kartezjański zbiorów stanów i i modyfikując funkcję przejścia, tak aby część stanów jest odpowiednio zaktualizowany, zachowując zachowanie ). $T$ $L$ $T$ $T'$ $L$ $T$ $L$ $L$ $T$

Gałąź z jest sekwencją tak, że jest przyjmowanie prosta droga w , a każdy jest silnie połączone elementem i których stany obejmują przeznaczenia (i pochodzenia ). Oddział jest oswojony, jeśli: $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}$

Długość wejściowa ścieżki jest większa lub równa jej długości wyjściowej; $\rho_1\rho_2\cdots\rho_{n+1}$
Dla dowolnego , dowolnego prostego cyklu w , wejściowa długość cyklu jest większa lub równa jego długości wyjściowej. $i$ $C_i$

Fakt: Dla każdego , implikuje wszystkie gałęzie są oswojone. $\big[$ $x, y$ $x[T']y$ $|y| \leq |x|$ $\big]$

Dowód jest raczej natychmiastowy. Ta ostatnia właściwość jest rozstrzygalna (ponieważ liczba rozgałęzień jest ograniczona, a także liczba prostych cykli), pokazuje to, że problem pytania jest rozstrzygalny.

— Michaël Cadilhac
źródło

Z opisu wynika, że jest nawet rozstrzygalny w NL (stąd w P), zakładając, że

jest podane przez FSA.

L

$L$

— Emil Jeřábek

Wysłałem Ci powiadomienie (przepraszam, że nie przeczytałem dokładnie Twojego komentarza przed opublikowaniem), ale prawdopodobnie nie otrzymałeś go po usunięciu odpowiedzi :-) ... ale teraz - w ramach zwrotu czasu - powinieneś zmienić na (i rozwiązać!) to jedno trudniejsze: " otwartym problemem : czy istnieje

i obliczalny kodowanie

takie, że dla wszystkich

?" :-D :-D

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

— Marzio De Biasi

@ EmilJeřábek Rzeczywiście, jest dość wyraźnie w ko-NL (stąd w NL).

— Michaël Cadilhac

@MarzioDeBiasi Thanks! Rzeczywiście nie widziałem twojego zawiadomienia ☺ Będę pracować nad zwrotem twojego czasu, gdy będę miał trochę ☺

— Michaël Cadilhac