4 papers
PVASS Reachability is Decidable
Roland Guttenberg, Eren Keskin, Roland Meyer
Reachability in pushdown vector addition systems with states (PVASS) is among the longest standing open problems in Theoretical Computer Science. We show that the problem is decida…
On the Separability Problem of VASS Reachability Languages
Eren Keskin, Roland Meyer
We show that the regular separability problem of VASS reachability languages is decidable and -complete. At the heart of our decision procedure are doubly-marked gra…
Separability in Büchi Vass and Singly Non-Linear Systems of Inequalities
Pascal Baumann, Eren Keskin, Roland Meyer +1
The omega-regular separability problem for Büchi VASS coverability languages has recently been shown to be decidable, but with an EXPSPACE lower and a non-primitive recursive uppe…
Separability and Non-Determinizability of WSTS
Wojciech CzerwiÅski, Eren Keskin, SÅawomir Lasota +4
We study the languages recognized by well-structured transition systems (WSTS) with upward and downward compatibility. Our first result shows that every pair of disjoint WSTS langu…