Regular separability of one counter automata

MaRDI QIDQ4968382zbMATH OpenFDO

Authors Wojciech Czerwiński, Sławomir Lasota

Publication date 12 July 2019

Full work available at URL https://arxiv.org/abs/1701.02808

zbMATH Keywords

one-counter automataone-counter netsregular separability problemvector addition systems with states

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Regular separability of one counter automata
• Regular separability of Parikh automata
• Separating regular languages with first-order logic
• Regular separability of well-structured transition systems
• Bisimulation equivalence and regularity for real-time one-counter automata

Cites work

• A Note on Decidable Separability by Piecewise Testable Languages
• Deciding piecewise testable separability for regular tree languages
• Efficient separability of regular languages by subsequences and suffixes
• First-order logic with reachability for infinite-state systems
• Going Higher in the First-Order Quantifier Alternation Hierarchy on Words
• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• scientific article; zbMATH DE number 176134 (Why is no real title available?)
• scientific article; zbMATH DE number 2038747 (Why is no real title available?)
• Invisible pushdown languages
• Lossy counter machines decidability cheat sheet
• Minimal solutions of linear diophantine systems : bounds and algorithms
• Noncanonical Extensions of Bottom-Up Parsing Techniques
• On the Decidability of Grammar Problems
• On the reachability problem for 5-dimensional vector addition systems
• Parallel program schemata
• Petri nets and regular languages
• Reachability for two-counter machines with one test and one reset
• Reachability in two-clock timed automata is PSPACE-complete
• Reachability in two-dimensional vector addition systems with states is PSPACE-complete
• Regular separability of one counter automata
• Regular separability of Parikh automata
• Regular separability of well-structured transition systems
• Separability of reachability sets of vector addition systems
• Separating regular languages by locally testable and locally threshold testable languages
• Separating regular languages by piecewise testable and unambiguous languages
• Separating regular languages with first-order logic
• Some algorithmic problems for pseudovarieties
• The complexity of regular abstractions of one-counter languages
• The taming of the semi-linear set

Cited in

(9)

• Regular separability of well-structured transition systems
• scientific article; zbMATH DE number 7559472 (Why is no real title available?)
• Regular separability of Parikh automata
• Regular separability of one counter automata
• Timed games and deterministic separability
• Separability in Büchi VASS and singly nonlinear systems of inequalities
• Verifying unboundedness via amalgamation
• Deterministic and game separability for regular languages of infinite trees
• Languages of boundedly-ambiguous vector addition systems with states

This page was built for publication: Regular separability of one counter automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4968382)