Kontekst: relacje między logiką a automatami
Twierdzenie Büchiego stwierdza, że logika Monadic drugiego rzędu nad łańcuchami (MSO) przechwytuje klasę zwykłych języków. Dowód faktycznie pokazuje, że egzystencjalne MSO ( lub EMSO ) nad łańcuchami wystarczy do przechwycenia zwykłych języków. Może to być nieco zaskakujące, ponieważ w ogólnych strukturach MSO jest bardziej wyraziste niż .
Moje (oryginalne) pytanie: minimalna logika dla zwykłych języków?
Czy istnieje logika, która w ciągu ogólnych struktur, jest ściśle mniej wyraziste niż , ale to nadal oddaje klasę języków regularnych gdy rozpatrywana przez strun?
W szczególności chciałbym wiedzieć, jaki fragment języków zwykłych jest przechwytywany przez FO nad ciągami, gdy jest rozszerzany za pomocą operatora o najmniej ustalonym punkcie (FO + LFP). Wygląda na naturalnego kandydata na to, czego szukam (jeśli nie jest to ).
Pierwsza odpowiedź
Zgodnie z odpowiedzią @ makoto-kanazawa , zarówno FO (LFP), jak i FO (TC) przechwytują więcej niż zwykłe języki, gdzie TC jest operatorem przechodniego zamykania relacji binarnych. Okaże się, czy TC może zostać zastąpiony przez innego operatora lub zestaw operatorów w taki sposób, że rozszerzenie przechwytuje dokładnie klasę zwykłych języków i żadnych innych.
Sama logika pierwszego rzędu, jak wiemy, nie wystarczy, ponieważ przechwytuje języki bez gwiazdek, odpowiednią podklasę zwykłych języków. Jako klasyczny przykład, język parzystości nie można wyrazić przy użyciu zdania FO.
Zaktualizowane pytanie
Oto nowe brzmienie mojego pytania, które pozostaje bez odpowiedzi.
Jakie jest minimalne rozszerzenie logiki pierwszego rzędu, tak że FO + to rozszerzenie, po przejęciu ciągów, przechwytuje dokładnie klasę zwykłych języków?
W tym przypadku rozszerzenie jest minimalne, jeśli jest najmniej wyraziste (po przejęciu ogólnych struktur) spośród wszystkich rozszerzeń przechwytujących klasę zwykłych języków (po przejęciu ciągów).
Odpowiedzi:
FO (LFP) przechwytuje PTIME na uporządkowanych strukturach, a łańcuchy są uporządkowanymi strukturami. Tak więc języki definiowane przez FO (LFP) obejmują wszystkie zwykłe języki i wiele więcej. http://dx.doi.org/10.1016/S0019-9958(86)80029-8
Podręcznik Ebbinghausa i Fluma zawiera ćwiczenie, w którym prosi się o pokazanie FO (TC ^ 1) (logika pierwszego rzędu rozszerzonego o przechodnie zamykanie relacji binarnych) jest równoważne MSO na łańcuchach. W tym samym ćwiczeniu jako przykład użyto aby pokazać, że FO (TC ^ 2) jest bardziej wyraziste niż MSO na łańcuchach. Wszystkie formuły FO (TC) są wyraźnie równoważne formułom FO (LFP).{anbn∣n≥1}
źródło
Ta odpowiedź jest nieco spóźniona, ale wiadomo, że można uzyskać wszystkie i tylko zwykłe języki, dołączając uogólniony kwantyfikator grupy dla każdej grupy skończonej (lub równoważnie dla każdej skończonej prostej grupy). Np. Patrz „Zwykłe języki definiowane przez Lindstrom Quantifiers” autorstwa Zoltana Esiky i Kim G. Larsen, pod adresem http://www.brics.dk/RS/03/28/BRICS-RS-03-28.pdf .
Co więcej, jest to optymalne w tym sensie, że zwykły język będzie definiowalny tylko wtedy, gdy dostępne będą kwantyfikatory dla każdej grupy dzielącej jego monoid składniowy.
źródło
To ćwiczenie 8.6.3 na stronie 221 drugiego wydania podręcznika Ebbinghaus i Fluma „ Teoria modeli skończonych” . Notacja FO (TCr ) jest tam wyjaśnione. FO (TCr ) może tworzyć przechodnie zamknięcie 2 r relacja -aryjna, traktowana jako relacja binarna r -platki
Znalazłem kilka referencji, które mogą Cię zainteresować.
FO (TC1 ) nazywa się FO (MTC) (logika pierwszego rzędu z monadycznym zamknięciem przechodnim) w dziesięciu artykułach Cate i Segoufin z 2010 r . Dowodzi to między innymi, że FO (MTC) jest ściśle mniej wyraziste niż MSO na skończonych drzewach.
Artykuł Bargury i Makowsky'ego z 1992 r. Pokazuje, że deterministyczne monadyczne przechodnie przechodnie - FO (DTC1 ) w notacji Ebbinghaus i Flum - wystarczy zdefiniować zwykłe języki strunowe (patrz Twierdzenie 5 w tym artykule).
źródło