Własność oddzielania

Speaker(s)

Henryk Michalewski

Affiliation

Uniwersytet Warszawski i IMPAN

Date

Nov. 16, 2011, 4:15 p.m.

Room

room 5050

Seminar

Topology and Set Theory Seminar

---

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.

---