Własność oddzielania

Prelegent(ci)

Henryk Michalewski

Afiliacja

Uniwersytet Warszawski i IMPAN

Termin

16 listopada 2011 16:15

Pokój

p. 5050

Seminarium

Seminarium „Topologia i teoria mnogości”

---

Pokażę, że własności oddzielania nie zachodzi dla klas Sigma_n (n>=2) w
hierarchii automatów alternujących na drzewach.  Dowód polega na
skonstruowaniu dwóch automatów, które zaświadczają o braku własności
oddzielania. Dla n=2 klasa Sigma_2 składa się ze zbiorów
koanalitycznychi  i powyższy wynik został wykazany we wcześniej pracy.
Dla n>2 klasy Sigma_n składają się ze zbiorów Delta^1_2.

Na potrzeby konstrukcji dla drzew zaanalizuję problem oddzielania dla
języków słów nieskończonych. W szczególności wskażę, które klasy
języków słów mają własność oddzielania. W przypadku drzew wiadome jest,
że oddzielanie zachodzi w klasie Pi_2 dualnej do Sigma_2 (tw. M.
Rabina), natomiast dla n>2 problem pozostaje otwarty.

---