5 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…
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 upper…
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 grap…
Urgency Annotations for Alternating Choices
Eren Keskin, Roland Meyer, Sören van der Wall
We propose urgency programs, a new programming model with support for alternation, imperfect information, and recursion. The novelty are urgency annotations that decorate the (ange…
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…