W teorii automatów (automaty skończone, automaty wypychające, ...) i złożoności występuje pojęcie „dwuznaczności”. Automat jest dwuznaczny, jeśli istnieje słowo z co najmniej dwoma odrębnymi przebiegami akceptującymi. Maszyna jest k- dwuznaczna, jeśli dla każdego słowa w zaakceptowanego przez maszynę istnieje co najwyżej k różnych przebiegów do zaakceptowania w .
Pojęcie to zdefiniowano także w gramatyce bezkontekstowej: gramatyka jest dwuznaczna, jeśli istnieje słowo, które można wyprowadzić na dwa różne sposoby.
Wiadomo również, że wiele języków ma ładną logiczną charakterystykę w stosunku do modeli skończonych. (Jeśli język jest regularny, istnieje monadyczna formuła drugiego rzędu ϕ nad słowami, tak że każde słowo w z L jest modelem ϕ , podobnie NP, jeśli jest równoważne formułom drugiego rzędu, w których istnieją kwantyfikatory drugiego rzędu.)
Stąd moje pytanie leży na obrzeżach dwóch domen: czy istnieje jakikolwiek wynik, a nawet kanoniczna definicja „dwuznaczności” formuł danej logiki?
Mogę sobie wyobrazić kilka definicji:
- nie jest niejednoznaczne, jeśli istnieje co najwyżej jeden x taki, że ϕ ( x ) utrzymuje, a ϕ ( x ) jest niejednoznaczny.
- byłby niejednoznaczny, gdyby istniał model zarówno ϕ 0, jak i ϕ 1 , lub jeśli ϕ i jest niejednoznaczny.
- Formuła SAT byłaby niejednoznaczna, jeśli istnieje co najwyżej jedno prawidłowe przypisanie.
Dlatego zastanawiam się, czy jest to dobrze znane pojęcie, w przeciwnym razie interesujące może być przeprowadzenie badań na ten temat. Jeśli to pojęcie jest znane, czy ktoś mógłby podać mi słowa kluczowe, których mógłbym użyć do wyszukiwania informacji w tej sprawie (ponieważ „dwuznaczność logiczna” daje wiele niepowiązanych wyników), lub odniesienia do książek / pdf / artykułów?
źródło
Tylko dwie uwagi. Mam nadzieję, że pomogą.
Standardowe definicje semantyki logiki i prawdy są zgodne z prezentacją Tarskiego, a następnie indukowane przez strukturę formuł. Inną możliwością jest zastosowanie semantyki opartej na grze, jak sugeruje Hintikka. Prawda i satysfakcja są zdefiniowane w kategoriach strategii w grze. W przypadku formuł pierwszego rzędu można udowodnić, że formuła jest prawdziwa pod pojęciem Tarskiego, tylko wtedy, gdy istnieje strategia wygrywająca w grze Hintikka.
W celu sformalizowania pytania można zapytać, czy gra dopuszcza wiele strategii. Istnieje również interesujące pytanie, czy strategie powinny być deterministyczne. Hintikka wymagała od nich determinizmu. Dowód, że oryginał Hintikki i semantyka Tarskiego są równoważne, wymaga Aksjomatu Wyboru. Można także sformalizować prawdę w kategoriach gier z niedeterministycznymi strategiami o mniejszej liczbie powikłań.
Twój przykład teorii języka przypomniał determinizm, relacje symulacyjne i akceptację języka. Relacja symulacji między automatami oznacza włączenie języka między ich językami, chociaż odwrotność nie jest prawdą. W przypadku automatów deterministycznych oba pojęcia są zbieżne. Można zapytać, czy możliwe jest „płynne” rozszerzenie relacji symulacji w celu uchwycenia równoważności języka dla automatów niedeterministycznych. Kousha Etessami ma naprawdę fajny artykuł pokazujący, jak to zrobić za pomocą symulacji k ( Hierarchia obliczeń wielomianowych w czasie dla automatów). Intuicyjnie „k” odzwierciedla stopień niedeterminizmu, jaki może uchwycić relacja symulacji. Kiedy „k” jest równe poziomowi niedeterminizmu w automacie, symulacja i równoważność językowa pokrywają się. Artykuł ten podaje także logiczną charakterystykę symulacji k pod względem poliadycznej logiki modalnej i ograniczonego fragmentu zmiennej logiki pierwszego rzędu. Włączenie języka, determinizm, gry, logika modalna i logika pierwszego rzędu - wszystko w jednym pakiecie zderzaka.
źródło
Zaczęło się od komentarza pod odpowiedzią Andreja Bauera, ale stało się zbyt duże.
Myślę oczywiste definicja niejednoznaczności z punktu widzenia teorii modelu skończonych widzenia byłoby: m b i g u o u s (ambiguous(ϕ)⟹∃M1,M2|M1⊨ϕ∧M2⊨ϕ∧M1⊨ψ∧M2⊭ψ
Innymi słowy, istnieją odrębne modele gramatyki zakodowane jako formuła którą można odróżnić za pomocą jakiejś formuły ψ , być może pod-formuły ϕϕ ψ ϕ .
Możesz połączyć to z odpowiedzią Andreja na dowody poprzez złożoność opisową. Kombinacja istnienia kodowania określonego modelu plus jego akceptacja przez odpowiednią TM jako model danej formuły JEST dowodem, że aksjomaty i wnioskowania (a zatem i równoważna gramatyka) zakodowane w tej formule są spójne.
Aby uczynić to w pełni kompatybilnym z odpowiedzią Andreja, należy powiedzieć, że model jest „generowany” przez formułę działającą jako filtr na przestrzeni wszystkich możliwych modeli skończonych (lub coś w tym rodzaju), z kodowaniem i działaniem filtrowania w modelu wejściowym jako „dowód”. Odrębne dowody świadczą o dwuznaczności.
To może nie być popularny sentyment, ale mam tendencję do myślenia o teorii modeli skończonych i teorii dowodu jako tej samej rzeczy widzianej pod różnymi kątami. ;-)
źródło
Nie jestem pewien, czy pytanie dotyczy CS, ale spróbuj wyszukać termin Nieokreśloność i logika. W filozofii logiki dwuznaczność zwykle odróżnia się od niejasności (patrz na przykład tutaj ) i myślę, że to, czego szukasz, jest niejasne (ponieważ niejasność jest definiowana jako terminy, w których występują przypadki graniczne). Główną książką w tej dziedzinie jest niejasność Timothy'ego Williamsona (ale także patrz bibliografia na stronie Stanford powyżej).
źródło
Ja (również) zgadzam się z Anrejem.
Myślę, że złożoność opisowa to charakterystyka bez obliczeń (co czyni ją interesującą na swój sposób), a zatem przykłady dwuznaczności obliczeniowej z teorii języków formalnych (automaty / gramatyki / ...), które sprawiły, że wyglądasz na zupełnie inną dziedzinę . W złożoności opisowej języki odpowiadają klasom złożoności, a zapytania (w języku) odpowiadają problemom obliczeniowym (nie algorytmom). Nie ma zamierzonego sposobu sprawdzania / obliczania zapytania AFAIK, więc jeśli nie szukasz obliczeniowej dwuznaczności, IMHO te przykłady wprowadzają w błąd.
źródło