Publication:4968382
From MaRDI portal
zbMath1440.68154arXiv1701.02808MaRDI QIDQ4968382
Sławomir Lasota, Wojciech Czerwiński
Publication date: 12 July 2019
Full work available at URL: https://arxiv.org/abs/1701.02808
vector addition systems with states; one-counter automata; one-counter nets; regular separability problem
68Q45: Formal languages and automata
68Q85: Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the reachability problem for 5-dimensional vector addition systems
- Petri nets and regular languages
- Reachability in two-clock timed automata is PSPACE-complete
- Parallel program schemata
- Separating Regular Languages with First-Order Logic
- Separating Regular Languages by Piecewise Testable and Unambiguous Languages
- A Note on Decidable Separability by Piecewise Testable Languages
- Separating Regular Languages by Locally Testable and Locally Threshold Testable Languages
- Lossy Counter Machines Decidability Cheat Sheet
- On the Decidability of Grammar Problems
- Noncanonical Extensions of Bottom-Up Parsing Techniques
- Deciding Piecewise Testable Separability for Regular Tree Languages
- The taming of the semi-linear set
- Reachability in Two-Dimensional Vector Addition Systems with States Is PSPACE-Complete
- The complexity of regular abstractions of one-counter languages
- First-order logic with reachability for infinite-state systems
- Invisible Pushdown Languages
- Separability of Reachability Sets of Vector Addition Systems
- Minimal solutions of linear diophantine systems : bounds and algorithms
- Going Higher in the First-Order Quantifier Alternation Hierarchy on Words
- Efficient Separability of Regular Languages by Subsequences and Suffixes