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).