Rozważamy modele dla PDL postaci skończonego łańcucha złożonego z dwóch programów atomowych: \(u\) i \(v\). Między każdymi dwoma kolejnymi stanami przechodzi jeden i tylko jeden z tych programów. Zmienne zdaniowe są dwie: \(p\) prawdziwa tylko w pierwszym stanie łańcucha i \(k\) prawdziwa tylko w ostatnim stanie. Innych zmiennych zdaniowych nie ma.
Każdą taką strukturę można naturalnie uważać również za strukturę pierwszego rzędu, wówczas \(u\) i \(v\) są relacjami dwuargumentowymi a \(p\) i \(k\) relacjami jednoargumentowymi.
Udowodnić, że dla każdego zdania \(\varphi\) logiki MSO istnieje zdanie \(\phi\) logiki PDL takie, że dla każdej struktury \(\mathfrak{A}\) jak powyżej, \(\varphi\) jest prawdziwe w stanie początkowym struktury \(\mathfrak{A}\) wtedy i tylko wtedy, gdy \(\mathfrak{A}\models\phi\).
Algebrę relacyjną z liniowym porządkiem na danych można skonstruować na dwa sposoby. Załózmy, że \(\leq\) jest relacją liniowego porządku na wszystkich elementach, które mogą się pojawić w krotkach, a w sygnaturze nie ma stałych.
Pierwszy sposób polega na tym, że do każdej bazy danych wprowadzamy dodatkową tabelę \(LEQ\) o dwóch kolumnach, która zawiera wszystkie krotki \(\langle a,b\rangle\) dla \(a,b\) należacych do aktywnej dziedziny i takich, że \(a\leq b.\) Wówczas zwykłe wyrażenia algebry relacyjnej mogą wykorzystać \(LEQ\) jak każdą inną tabelę. Jednak \(LEQ\) uważamy za część składni zapytań, a nie zwykłą tabelę w bazie.
Drugi sposób polega na tym, że nie zwiększamy liczby tabel, ale poszerzamy składnię i w warunku \(\theta\) selekcji \(\sigma_\theta(E)\) dopuszczamy także nierówności postaci \(i\leq j\) dla \(i,j\) nie większych niż liczba kolumn w \(E\). Semantyka jest oczywista, np. \([\![\sigma_{i\leq j}(E)]\!]=\{\vec{a}\in [\![E]\!]:a_i\leq a_j\}.\)
Pokazać, że zbiory zapytań wyrażalnych w obu formalizmach są takie same.
Wykazać, że dla każdego ustalonego skończonego grafu \(\mathfrak{G}\) (ta litera to gotyckie G) i każdego ustalonego \(m\in\mathbb{N}\), następujący problem decyzyjny może zostać rozstrzygnięty przez deterministyczną maszynę Turinga, która obok taśmy z danymi tylko do odczytu ma taśmę roboczą o długości \(O(\log n)\) (za \(n\) przyjmujemy długość danych wejściowych algorytmu):
Dany: kod skończonego grafu \(\mathfrak{H}\) (gotyckie H) w postaci macierzy incydencji podanej wierszami.
Pytanie: Czy gracz II ma strategię wygrywającą w grze \(G_m(\mathfrak{G},\mathfrak{H})\)?
Czy następująca formuła logiki drugiego rzędu jest tautologią dla \(n>1\):
\(\forall E\left[\left(\begin{array}{c}\forall xE(x,x)\land\\ \forall xy(E(x,y)\to E(y,z))\land\\ \forall xyz((E(x,y)\land E(y,z))\to E(x,z)))\end{array}\right)\to\forall x_{1}\dots x_{n}\ \bigvee _{{0\leq i< j\leq n}}E(x_{i},x_{j}))\right]\) \(\to\) \((\exists y_{1}\ldots y_{{n-1}}\forall z\bigvee _{{i=1}}^{{n-1}}y_{i}=z)\)
Odpowiedz TAK lub NIE na wybrane trzy spośród poniższych pytań. Każda poprawna odpowiedź daje \(0.5\) punkta, każda niepoprawna \(-0.5\) punkta. W razie udzielenia odpowiedzi na więcej pytań, do wyniku zaliczymy trzy najgorsze z nich. Odpowiedzi proszę pisać na tej kartce!