Nie jesteś zalogowany |
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).
