You are not logged in |
Regular Separability of One Counter Automata
- Speaker(s)
- Sławomir Lasota
- Affiliation
- Uniwersytet Warszawski
- Date
- Jan. 25, 2017, 2:15 p.m.
- Room
- room 5870
- Seminar
- Seminar Automata Theory
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).
