Regular Separability of One Counter Automata

Prelegent(ci)

Sławomir Lasota

Afiliacja

Uniwersytet Warszawski

Termin

25 stycznia 2017 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

The regular separability problem asks, for two given languages, if there exists a regular language including one of them but disjoint from the other. We show that regular separability problem is undecidable for one counter automata, but decidable (and PSPACE-complete) for one counter automata without zero tests (aka 1-dimensional vector addition systems with states).

---