Automaty a rekurencja 2016/2017

[up]

Zadania domowe (ostatnia aktualizacja: 23.12.2016 - obecnie jest 6 zadań)

24.01.2017

Wykład

Udowodniliśmy, że wszystkie grafy w hierarchii Caucala można uzyskać wykonując interpretacje tylko w drzewach deterministycznych (zamiast we wszystkich). Ponadto udowodniliśmy, że grafy na n-tym poziomie hierarchii Caucala to dokładnie epsilon-ściągnięcia grafów konfiguraji automatów ze stosem rzędu n (bez collapse). Według tego artykułu. Uzasadniliśmy też, że grafy w hierarchii Caucala mają rozstrzygalną logikę MSO, w przeciwieństwie do grafów konfiguracji automatów ze stosem wyższego rzędu z collapse.

Ćwiczenia

  1. Omówienie zadań zaliczeniowych.

17.01.2017

Wykład

Udowodniliśmy, że deterministyczna hierarchia Caucala jest zamknięta na MSO-transdukcje oraz na operację "treegraph". Według tego artykułu.

Ćwiczenia

  1. Istnieje graf G oraz MSO-interpretacja I takie, że grafu I(G) nie da się uzyskać z G za pomocą odwrotnego przekształcenia regularnego.
  2. Istnieje graf G oraz MSO-transdukcja t takie, że grafu t(G) nie da się uzyskać z G za pomocą MSO-interpretacji.

10.01.2017

Wykład

Zdefiniowaliśmy hierarchię Caucala oraz MSO-interpretacje i MSO-transdukcje. Według tego artykułu.

Ćwiczenia

  1. Istnieje graf G oraz MSO-transdukcja t takie, że grafu t(G) nie da się uzyskać z G za pomocą MSO-interpretacji.

20.12.2016

Wykład

Udowodniliśmy, że automaty ze stosem rzędu n (niedeterministyczne / deterministyczne, z collapse lub bez) mogą rozpoznać więcej języków niż automaty ze stosem rzędu n-1. Udowodniliśmy, że niedeterministyczne automaty ze stosem rzędu n i z wieloma dwukierunkowymi głowicami rozpoznają dokładnie wszystkie języki z klasy (n-1)-EXPTIME. Według tego artykułu.
Zobacz notatki napisane przez Rafała Stefańskiego.

Ćwiczenia

  1. Automat używający dodatkowej pamięci logarytmnicznej można zamienić na automat z wieloma (dwukierunkowymi) głowicami.
  2. Automaty ze stosem rzędu n (niedeterministyczne / deterministyczne, z collapse lub bez) generują więcej drzew niż automaty ze stosem rzędu n-1.
  3. Dowolny niedeterministyczny automat ze stosem rzędu 2 można zamienić na automat nie używający operacji collapse.

13.12.2016

Wykład

Udowodniliśmy n-EXPTIME-trudność problemu: czy drzewo generowane przez dany schemat rekurencyjny rzędu n jest akceptowane przez dany automat na drzewach. Udowodniliśmy (n-1)-EXPTIME-trudność problemu: czy drzewo generowane przez dany schemat rekurencyjny rzędu n zawiera literę a. Według tego artykułu.
Zobacz notatki.

Ćwiczenia

  1. Automaty z trywialnym warunkiem akceptacji i z kotrywialnym warunkiem akceptacji rozpoznają klasy języków będących nawzajem swoimi dopełnieniami.
  2. Język "U" można rozpoznać deterministycznym automatem rzędu 2 z collapse / niedeterministycznym bez collapse.
  3. Dowolny niedeterministyczny automat ze stosem rzędu 2 można zamienić na automat nie używający operacji collapse.

6.12.2016

Wykład

Znów rozważaliśmy problem: czy drzewo generowane przez dany schemat rekurencyjny jest akceptowane przez dany automat na drzewach. Tym razem omówiliśmy algorytm, który ma szansę działać w praktyce, na typowych danych wejściowych (czyli nie tworzy od razu obiektów wielokrotnie wykładniczego rozmiaru, w przeciwieństwie do poprzednio poznanego algorytmu). Według tego artykułu.
Zobacz notatki.

Ćwiczenia

  1. Przykłady do wykładu (jak algorytm działa dla konkretnego wejścia).
  2. Automaty z trywialnym warunkiem akceptacji i z kotrywialnym warunkiem akceptacji rozpoznają klasy języków będących nawzajem swoimi dopełnieniami.

29.11.2016

Wykład

Ustalmy jakiś model dla rachunku lambda-Y. Pokazaliśmy jak wzbogacić dany lambda-Y term tak, aby w każdym wierzchołku generowanego drzewa oprócz oryginalnej etykiety wypisywał wartość w modelu dla poddrzewa zaczynającego się w tym miejscu.
Według tego artykułu, strony 23-24.
Zobacz notatki napisane przez Marka Sommera.

Ćwiczenia

  1. Rozstrzyganie, czy każde skończone drzewo generowane przez dany niedeterministyczny HORS należy do danego języka regularnego (przez redukcję do pojedynczego drzewa nieskończonego).

22.11.2016

Wykład

Pokazaliśmy jak skonstruować model dla rachunku lambda-Y, który pozwala stwierdzić, czy dany automat akceptuje drzewo generowane przez term. Według tego artykułu, strony 7-9.
Zobacz notatki.

Ćwiczenia

  1. Własność Churcha-Rossera dla rachunku lambda-Y (przemienność redukcji).
  2. Standaryzacja (zawsze możemy zaczynać od redukcji czołowych).
  3. Równoważność między HORS i CPDA działa także w przypadku niedeterministycznym (kodowanie języka drzew w jednym drzewie nieskończonym).

15.11.2016

Wykład

Najpierw pokazaliśmy jak zamienić automat CPDA na schemat rekurencyjny (mniej więcej według tego artykułu - strony 14-23).
Następnie zdefiniowaliśmy pewien rodzaj automatów skończonych rozpoznających drzewa nieskończone: niedeterministyczne automaty z trywialnym warunkiem akceptacji. Zdefiniowaliśmy także czym jest model dla rachunku lambda-Y. Ta druga część naśladuje nieco to, co jest napisane w tym artykule.
Zobacz notatki.

Ćwiczenia

  1. Drzewo generowane przez lambda-Y term jest jednoznacznie wyznaczone (nie zależy od kolejności wykonywania redukcji).
  2. Jeśli w termie nie ma żadnego Y, to zaczyna się w nim pewien skończony ciąg redukcji, którego nie można przedłużyć.

8.11.2016

Wykład

Idziemy nadal mniej więcej według tego artykułu (z pewnymi zmianami notacyjnymi). Dzisiaj:
  1. definicja maszyny Krivine'a (str. 9-10),
  2. tłumaczenie z termu lambda-Y (a dokładniej z maszyny Krivine'a) do automatu CPDA, rzędu o jeden gorszego niż można (str. 23-26),
  3. rząd można poprawić o 1 gdy term jest w postaci kanonicznej (str. 29).
Zobacz notatki.

Ćwiczenia

  1. Transformacja z wykładu na przykładach.
  2. Drzewo generowane przez lambda-Y term jest jednoznacznie wyznaczone (nie zależy od kolejności wykonywania redukcji).

25.10.2016

Wykład

Tłumaczenie termu rachunku lambda-Y na równoważny schemat rekurencyjny, mniej więcej wg tego artykułu, strony 16-21:
  1. prostsze tłumaczenie, zwiększające rząd o 1,
  2. sprawadzanie termu do postaci kanonicznej (nie zmieniające rzędu),
  3. tłumaczenie dla termów w postaci kanonicznej, nie zmieniające rzędu.
Zobacz notatki napisane przez Rafała Stefańskiego.

Ćwiczenia

  1. Transformacja z wykładu na przykładach.
  2. Drzewo generowane przez lambda-Y term jest jednoznacznie wyznaczone (nie zależy od kolejności wykonywania redukcji).

18.10.2016

Wykład

  1. Otypowany rachunek lambda-Y - definicja; drzewo generowane przez term.
  2. Tłumaczenie schematu rekurencyjnego na równoważny term rachunku lambda-Y, wg tego artykułu, strona 15.
Zobacz notatki napisane przez Marka Sommera.

Ćwiczenia

  1. Skonstruuj schemat rekurencyjny rzędu 2 generujący drzewo, którego gałęzie to a^k b^{2^k}.
  2. Skonstruuj schemat rekurencyjny rzędu 3 generujący drzewo, którego gałęzie to a^k b^{2^{2^k}}.
  3. Skonstruuj 3-PDA dla {a^(2^(2^n))}.
  4. Udowodnij poprawność tłumaczenia z wykładu.

11.10.2016

Wykład

Schematy rekurencyjne - definicja i przykłady; drzewo generowane przez schemat rekurencyjny.
Zobacz notatki napisane przez Roberta Błaszkiewicza.

Ćwiczenia

Schematy rekurencyjne rzędu 1 i gramatyki bezkontekstowe są równoważne.
Idea: Z gramatyki do schematu - prosto. W drugą stronę - dokładnie odwrotne tłumaczenie możemy zrobić przy założeniu, że w schemacie mamy tylko nieterminale biorące co najwyżej jeden argument, przy czym (jeśli argument jest, to) musi on występować po prawej stronie reguł. Dla dowolnego schematu musimy najpierw sprowadzić do tej postaci (co jest możliwe, bo "i tak co najwyżej jeden argument zostanie użyty").

4.10.2016

Wykład

Wprowadzenie - slajdy

Ćwiczenia

  1. Języki K, L - bezkontekstowe. Czy są bezkontekstowe:
  2. Czy są rozstrzygalne dla K, L bezkontekstowych:
  3. Czy dla każdego automatu ze stosem istnieje deterministyczny automat ze stosem rozpoznający ten sam język? (przykład: a^n b^2n + a^n b^n)
  4. Zad 1 oraz 2a,b,c dla deterministycznych automatów ze stosem.
  5. Przypomnienie redukcji: automat ze stosem <-> gramatyka bezkontekstowa.
  6. Skonstruuj 2-PDA dla {a^n b^n c^n}.
  7. Skonstruuj 3-PDA dla {a^(2^(2^n))}.