On the separability problem of VASS reachability languages

DOI10.1145/3661814.3662116MaRDI QIDQ6970224zbMATH OpenFDO

Authors Eren Keskin, Roland Meyer

Publication date 18 June 2025

Full work available at URL https://doi.org/10.1145/3661814.3662116

zbMATH Keywords

Petri netsreachability languagesregular separabilityVASS

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Cites work

• A structure to decide reachability in Petri nets
• An Approach to Regular Separability in Vector Addition Systems
• Complexity hierarchies beyond elementary
• Demystifying Reachability in Vector Addition Systems
• scientific article; zbMATH DE number 3237829 (Why is no real title available?)
• Improved Ackermannian lower bound for the Petri nets reachability problem
• Invisible pushdown languages
• Marked directed graphs
• On selective unboundedness of VASS
• On the separability problem of VASS reachability languages
• Parallel program schemata
• Reachability in vector addition systems is Ackermann-complete
• Reachability in vector addition systems is primitive-recursive in fixed dimension
• Regular separability in Büchi VASS
• Regular separability of one counter automata
• Regular separability of Parikh automata
• Regular separability of well-structured transition systems
• Regular separators for VASS coverability languages
• Separability and non-determinizability of WSTS
• Separability of reachability sets of vector addition systems
• Synchronisationsgraphen
• The covering and boundedness problems for vector addition systems
• The reachability problem for Petri nets is not primitive recursive
• Timed games and deterministic separability
• Vector addition system reachability problem, a short self-contained proof

Cited in

(4)

• 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
• Languages of boundedly-ambiguous vector addition systems with states

This page was built for publication: On the separability problem of VASS reachability languages

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