You are not logged in | Log 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).