2024/10/01 by Elias Rojas Collins, Collins, Elias Rojas, Chris Köcher +3
Computer Science · #Advanced Algebra and Logic #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Machine Learning and Algorithms #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2410.00548
openalex publication_date 2024/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In a separability problem, we are given two sets K and L from a class C, and we want to decide whether there exists a set S from a class S such that K⊆ S and S∩ L=∅. In this case, we speak of \emphseparability of sets in C by sets in S. We study two types of separability problems. First, we consider separability of semilinear sets (i.e. subsets of ℕd for some d) by sets definable by quantifier-free monadic Presburger formulas (or equivalently, the recognizable subsets of ℕd). Here, a formula is monadic if each atom uses at most one variable. Second, we consider separability of languages of Parikh automata by regular languages. A Parikh automaton is a machine with access to counters that can only be incremented, and have to meet a semilinear constraint at the end of the run. Both of these separability problems are known to be decidable with elementary complexity. Our main results are that both problems are coNP-complete. In the case of semilinear sets, coNP-completeness holds regardless of whether the input sets are specified by existential Presburger formulas, quantifier-free formulas, or semilinear representations. Our results imply that recognizable separability of rational subsets of Σ^*×ℕd (shown decidable by Choffrut and Grigorieff) is coNP-complete as well. Another application is that regularity of deterministic Parikh automata (where the target set is specified using a quantifier-free Presburger formula) is coNP-complete as well.