2020/01/01 by Wojciech Czerwiński, Czerwiński, Wojciech, Georg Zetzsche +1 · 3 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Chemical Synthesis and Analysis #DNA and Biological Computing #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2007.00111
openalex publication_date 2020/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the problem of regular separability of languages of vector addition systems with states (VASS). It asks whether for two given VASS languages K and L, there exists a regular language R that includes K and is disjoint from L. While decidability of the problem in full generality remains an open question, there are several subclasses for which decidability has been shown: It is decidable for (i) one-dimensional VASS, (ii) VASS coverability languages, (iii) languages of integer VASS, and (iv) commutative VASS languages. We propose a general approach to deciding regular separability. We use it to decide regular separability of an arbitrary VASS language from any language in the classes (i), (ii), and (iii). This generalizes all previous results, including (iv).