Dlaczego automaty z ograniczeniem liniowym nie są tak popularne jak inne automaty?

9

Z mojego doświadczenia wynika, że języki kontekstowe i automaty z ograniczeniami liniowymi są często pomijane lub przewijane na kursach teorii obliczeń, a nawet są pomijane w niektórych znaczących podręcznikach, chociaż automaty skończone i zmniejszające są bardzo popularne. Z pewnością musi istnieć dobry powód, dla którego LBA są mniej skoncentrowane niż ich odpowiedniki?

computability fl.formal-languages automata-theory

— goric
źródło

Zobacz to pytanie: Czy hierarchia Chomsky'ego jest przestarzała?

— Kaveh

Czy możesz wyjaśnić, jak odnosi się powiązane pytanie, Kaveh? (Ponieważ nie sądzę, aby jego ton był tutaj pomocny, ale indywidualne odpowiedzi mogą być)

— Raphael

2

@Raphael: Odpowiedzi na pytanie Kaveha wyjaśniły, dlaczego języki kontekstowe nie są uważane za tak ważne jak wcześniej: krótko mówiąc, należy rozważyć inne, bardziej interesujące modele. (więcej)

— Tsuyoshi Ito

2

(kont.) Ten sam powód dotyczy „automatów z ograniczeniami liniowymi”. To zabawne, że nigdy nie słyszałem o tym imieniu. Dla mnie są to po prostu deterministyczne / niedeterministyczne maszyny Turinga w przestrzeni O (n) i nie rozumiem, dlaczego powinniśmy wyróżniać maszyny w przestrzeni O (n) (zamiast przestrzeni wielomianowej lub przestrzeni O (log n) lub cokolwiek innego), chociaż musiał istnieć powód historyczny. Ponadto ani klasa DSPACE (O (n)), ani NSPACE (O (n)) nie są zamknięte w ramach wywołań podprogramów .

— Tsuyoshi Ito

1

Tsuyoshi, moja interpretacja tego pytania jest taka, że naucza się FA, PDA i reszty Hierarchii Chomsky'ego (według równie nudnego rozumowania twoich odpowiedzi), ale LBA nie.

— Raphael

13

Dzięki „odpowiednim” modyfikacjom możemy zamienić te klasy w klasy złożoności; Skończone automaty w $NC^1$ , CFL do LogCFL i LBA do PSPACE.

Teraz powinno być całkiem jasne, dlaczego interesują nas pierwsze dwa bardziej niż LBA. Pierwsze dwa naturalnie pasują do zwykłej definicji wykonalnego obliczenia. Ale PSPACE nie.

— V Vinay
źródło

1

przekształcenie LBA w PSPACE brzmi prawie jak przestrzeń liniowa, wszystko czego potrzebujesz, aby uchwycić PSPACE, co oczywiście nie może być prawdą. Więc jaki jest mój błąd w myśleniu?

— Suresh Venkat

2

@Suresh: Istnieją następujące połączenia. Klasą problemów, które można (NC1-) zredukować do zwykłych języków, jest NC1, klasą problemów (log-space-) redukowalną do CFL jest LogCFL, a klasą problemów (NC1- lub log-space-) redukowalną do LBA jest PSPACE. Nie jestem pewien, czy możemy zastosować to samo pojęcie redukowalności we wszystkich tych trzech przypadkach.

— Tsuyoshi Ito

Zawierający kompletny problem dla innej klasy (nawet poniżej

A C^{0}

$AC^0$ redukcje) nie wydaje się dobrym powodem, aby klasa była interesująca.

— Kaveh

3

Zapytaj swojego profesora, dlaczego to zrobił. Mogę tylko zgadywać.

Nie są tak interesujące jak kompletne modele Turinga i PDA, ponieważ są w próżni bezużyteczności *, oczywiście, dzielą się swoim językowym odpowiednikiem: nie tak potężnym, jak to możliwe, ale już bardzo trudnym do rozwiązania.

Innym powodem może być to, że niewiele wiadomo na ich temat (zgadując tutaj), ale może to sprowadzać się do problemu jaja kurzego.

Jest niejasna pogoda $NLBA = DLBA$ , co może stanowić problem dla dydaktyki. Ponadto typowe dowody (np. Akceptowany język, odpowiedniki modeli) są znacznie trudniejsze niż w przypadku innych modeli.

(*) celowa przesada

— Raphael
źródło

2

Wygląda na to, że nie tylko CSG, ale także CFG ... są obecnie modne. Myślę, że w dzisiejszych czasach automaty i PDA są zwykle rozważane na kursach teorii obliczalności / złożoności (jeśli w ogóle) i tam są one uwzględniane nie dla nich samych, ale w celu wprowadzenia maszyn Turinga.

Gramatyki są prawdopodobnie interesujące z punktu widzenia teorii kompilatorów, ale nie tyle ze względu na możliwość obliczenia / złożoności, które należy uwzględnić we wstępnym kursie licencjackim. Jest zbyt wiele tematów, które chcielibyśmy omówić, ale jeden semestralny kurs jest po prostu zbyt krótki i musimy wybrać i wiele z tych tematów, których nie możemy omówić z powodu ograniczeń czasowych, są o wiele bardziej interesujące niż LBA.

— Kaveh
źródło

1

Chciałbym, żebyś był ogólnie prawdziwy! Zajęcia wprowadzające do TCS prowadzone w moim univ to pół automaty / CFL. Uczęszczam na te zajęcia, a uczniowie wydają się naprawdę daleki od zainteresowania. Może to być kolejny powód, dla którego CFL / CSL nie są już prezentowane: są tematy, które są o wiele bardziej ekscytujące.

— Michaël Cadilhac 27.01.11

1

Cóż, teoria CS to nie tylko złożoność. W szczególności CFG oraz powiązane modele automatów są bardzo ważne (przynajmniej jako fundamenty) w wielu gałęziach CS. Kurs wprowadzający powinien przygotować cię do wszystkich gałęzi. Przepraszam, ale ta odpowiedź pachnie ignorancją. Ponadto nie odpowiada na pytanie.

— Raphael

@ Rafael, mówię o kursach teorii obliczalności / złożoności, w których teoria automatów jest rozważana na znanych mi uniwersytetach. Nikt nic nie mówił o kursach teoretycznych w ogóle. Myślę, że powinieneś uważnie czytać posty, zanim oskarżysz innych o ignorancję. Mój post odpowiada na pytanie: dlaczego LBA nie jest brany pod uwagę w kursach teorii obliczalności / złożoności? To jest powód i dlatego podręczniki teorii obliczalności i złożoności nie zawierają zbyt wiele informacji na temat LBA, czy ci się to podoba, czy nie.

— Kaveh

Czyli jesteś prywatny z powodów osobistych każdego autora i wykładowcy na całym świecie? Tak jasne. W każdym razie należy pamiętać, że słowo „złożoność” w ogóle nie występuje w wysłanym pytaniu. Zauważ też, że w komentarzu powyżej i edycji nie odpowiedziałeś na pytanie. Fakt, czy ci się to podoba, czy nie.

— Raphael

1

@ Rafael, wciąż nie czytasz uważnie i nadal interpretujesz to, co piszę tak, jak wolisz, wydaje mi się, że po prostu chcesz się kłócić, myślę, że mój punkt widzenia jest wystarczająco jasny, dlatego możesz swobodnie myśleć tak, jak chcesz. :)

— Kaveh

2

Wyrażenia regularne i CFG są używane w praktyce do parsowania kodu (czyli języków programowania). Powodem jest to, że istnieją bardzo wydajne algorytmy do ich analizowania. Z drugiej strony, LBA są zbyt potężne, aby faktycznie je stosować w tym kontekście.

Historyczne pochodzenie teorii automatów jest przedmiotem budowy kompilatora. Z powyższego powodu tylko zwykłe języki i CFG są przydatne do konstruowania kompilatorów (pomimo faktu, że gramatyki atrybucyjne nie są tak naprawdę CFG, a algorytmy parsowania CFG tak naprawdę nie analizują całej klasy CFG). LBA mogły zostać wynalezione przez Chomsky'ego jako pewien pośredni poziom złożoności między przyziemnym a „angielskim”. Być może więc właściwym miejscem do ich nauczania są kursy lingwistyczne, a nie informatyczne!

— Yuval Filmus
źródło

Ponieważ LBA są równoważne z całkiem naturalną klasą gramatyk kontekstowych, nie sądzę, że zostały wymyślone dla zabawy. ;)

— Raphael

@Raphael: Yuval wcale tego nie sugerował.

— reinierpost