Regular separators for VASS coverability languages

DOI10.4230/LIPICS.FSTTCS.2023.15MaRDI QIDQ6951723zbMATH OpenFDO

Authors Chris Köcher, Georg Zetzsche

Publication date 28 July 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.FSTTCS.2023.15

zbMATH Keywords

regular languageseparabilityvector addition system

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Cites work

• A characterization for decidable separability by piecewise testable languages
• A generic polynomial time approach to separation by first-order logic without quantifier alternation
• An Approach to Regular Separability in Vector Addition Systems
• Complexity analysis of the backward coverability algorithm for VASS
• Coverability in VASS revisited: improving Rackoff's bound to obtain conditional optimality
• Deciding piecewise testable separability for regular tree languages
• Efficient separability of regular languages by subsequences and suffixes
• scientific article; zbMATH DE number 3628412 (Why is no real title available?)
• scientific article; zbMATH DE number 7799624 (Why is no real title available?)
• Invisible pushdown languages
• It is Undecidable if Two Regular Tree Languages can be Separated by a Deterministic Tree-walking Automaton
• Noncanonical Extensions of Bottom-Up Parsing Techniques
• On the Decidability of Grammar Problems
• Regular Separability and Intersection Emptiness Are Independent Problems
• Regular separability in Büchi VASS
• Regular separability of one counter automata
• Regular separability of Parikh automata
• Regular separability of well-structured transition systems
• Remarks on blind and partially blind one-way multicounter machines
• Separability by piecewise testable languages and downward closures beyond subwords
• Separability by piecewise testable languages is \textsc{PTime}-complete
• Separability of rational relations in A^* N^m by recognizable relations is decidable
• Separability of reachability sets of vector addition systems
• Separating regular languages by locally testable and locally threshold testable languages
• Separating regular languages with first-order logic
• Separating regular languages with first-order logic
• Separating Without Any Ambiguity.
• Separation and covering for group based concatenation hierarchies
• Separation and the successor relation
• Separation for dot-depth two
• The covering and boundedness problems for vector addition systems
• Well-structured transition systems everywhere!

Cited in

(3)

• Separability in Büchi VASS and singly nonlinear systems of inequalities
• On the separability problem of VASS reachability languages
• The complexity of separability for semilinear sets and Parikh automata

This page was built for publication: Regular separators for VASS coverability languages

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