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

10

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 ] y x x [ T ] yT[T]yxx[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?TL
xLyx[T]y|y||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
2
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. x|F(x)|x
Michaël Cadilhac
| 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)|ϵ
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. L T T L | T ( w ) | | w | w L T TLTTL|T(w)||w|wLT
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

Odpowiedzi:

8

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 ).L T T L T L L TT.L.T.T.L.T.L.L.T.

Gałąź z jest sekwencją tak, że jest przyjmowanie prosta droga w T " , a każdy C i jest silnie połączone elementem T " i których stany obejmują przeznaczenia ρ i (i pochodzenia ρ i + 1 ). Oddział jest oswojony, jeśli:ρ 1 C 1 ρ 2 C 2ρ n C n ρ n + 1 ρ 1 ρ 2ρ n + 1T.ρ1do1ρ2)do2)ρndonρn+1ρ1ρ2)ρn+1T.dojaT.ρjaρja+1

  1. Długość wejściowa ścieżki jest większa lub równa jej długości wyjściowej;ρ1ρ2)ρn+1

  2. Dla dowolnego , dowolnego prostego cyklu w C i , wejściowa długość cyklu jest większa lub równa jego długości wyjściowej.jadoja

Fakt: Dla każdego x , y , x [ T ] y implikuje | y | | x | ] wszystkie gałęzie są oswojone.[x,yx[T.]y|y||x| ]

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
1
Z opisu wynika, że ​​jest nawet rozstrzygalny w NL (stąd w P), zakładając, że jest podane przez FSA. 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 S n takie, że dla wszystkich k 1 , L S nn = L S nn + k ?" :-D :-Dn1Snk1LnSn=Ln+kSn
Marzio De Biasi
1
@ 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