Regular separability of Parikh automata

DOI10.4230/LIPICS.ICALP.2017.117MaRDI QIDQ5111449zbMATH OpenFDO

Authors Lorenzo Clemente, Wojciech Czerwiński, Sławomir Lasota, Charles Paperman

Publication date 27 May 2020

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

zbMATH Keywords

decidabilityinteger vector addition systemsParikh automataregular separability problemundecidabilityvisible one-counter automata

Mathematics Subject Classification ID

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 one counter automata
• Efficient separability of regular languages by subsequences and suffixes
• Separating regular languages by piecewise testable and unambiguous languages
• Separating regular languages with first-order logic

Cited in

(19)

• Learning algorithms
• Bounded Parikh automata
• scientific article; zbMATH DE number 3943060 (Why is no real title available?)
• Regular separability of one counter automata
• Unboundedness problems for languages of vector addition systems
• Regular separability of well-structured transition systems
• scientific article; zbMATH DE number 7559472 (Why is no real title available?)
• Regular separability of one counter automata
• Unboundedness problems for machines with reversal-bounded counters
• Timed games and deterministic separability
• Separability in Büchi VASS and singly nonlinear systems of inequalities
• History-deterministic Parikh automata
• Counter machines with infrequent reversals
• Regular separators for VASS coverability languages
• History-deterministic Parikh automata
• Separability and non-determinizability of WSTS
• On the separability problem of VASS reachability languages
• Deterministic and game separability for regular languages of infinite trees
• The complexity of separability for semilinear sets and Parikh automata

This page was built for publication: Regular separability of Parikh automata

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