Twierdzenie Immermana- Vardiego stwierdza, że PTIME (lub P) to właśnie klasa języków, którą można opisać zdaniem logiki pierwszego rzędu wraz z operatorem punktu stałego, nad klasą uporządkowanych struktur. Operator punktu stałego może być albo najmniejszym punktem stałym (według Immermana i...
Czy możliwe jest algorytmiczne testowanie, czy liczba obliczalna jest liczbą wymierną czy całkowitą? Innymi słowy, możliwe byłoby dla biblioteki, który implementuje numery obliczalne, aby zapewnić funkcje isIntegerlub isRational? Zgaduję, że nie jest to możliwe i że jest to w jakiś sposób związane...
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...
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 ( ∃MSO∃MSO\exists\text{MSO} lub EMSO ) nad łańcuchami wystarczy do...
Problem z utrzymaniem porządku (lub „utrzymaniem porządku na liście”) polega na obsłudze operacji: singleton: tworzy listę z jednym elementem, zwraca do niej wskaźnik insertAfter: dany wskaźnik do elementu wstawia nowy element po nim, zwracając wskaźnik do nowego elementu delete: dany wskaźnik do...
Wiem, że pytanie „czy formuła pierwszego rzędu ma model” jest ogólnie nierozstrzygalne.ϕϕ\phi Czy ktoś mógłby mi dać link lub książkę, która da odpowiedź na skończone modele. Jeśli mam wzór pierwszego rzędu , czy można rozstrzygnąć, czy ϕ ma model skończony? Jestem pewien, że pytanie jest dobrze...
Wydaje się, że w popularnych językach zapytań dotyczących relacyjnych baz danych możliwe jest tworzenie zapytań, które będą wymagały dużej ilości zasobów. W praktyce administratorzy baz danych zarządzają tym, ograniczając ilość pamięci na zapytanie i sprawdzając, czy w bazie danych nie ma żadnych...
Moje pytanie dotyczy teorii modeli skończonych / złożoności opisowej, więc FO(R)FO(R)FO(R) będzie oznaczać „pierwszy rząd nad skończonymi słowami binarnymi, przy użyciu predykatów Rs i jednoargumentowego predykatu P true na pozycji 1 w słowie”. Chciałbym wiedzieć, czy jest jakakolwiek...
Aby lepiej zrozumieć artykuł, staram się krótko zrozumieć logikę najmniej ustalonego punktu. Utknąłem w kilku punktach. Gdyby G = ( V, E)G=(V,E)G = (V,E) jest wykresem i Φ ( str) = { ( a , b ) ∣ G ⊨ E( a , b ) ∨ P( a , b ) ∨ ∃ z( E( a , z) ∧ P( z, b ) )