2026-07-20T11:15:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24145 2025-11-12T13:33:37Z ddc:004 open_access

The Complexity of Separability for Semilinear Sets and Parikh Automata Collins, Elias Rojas Köcher, Chris Zetzsche, Georg Vector Addition System Separability Regular Language In a separability problem, we are given two sets K and L from a class 𝒞, and we want to decide whether there exists a set S from a class 𝒮 such that K ⊆ S and S ∩ L = ∅. In this case, we speak of separability of sets in 𝒞 by sets in 𝒮. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Elias Rojas Collins and Chris Köcher and Georg Zetzsche 2025 Is Part Of LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2025.38 urn:nbn:de:0030-drops-241457 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.38 eng https://creativecommons.org/licenses/by/4.0/legalcode