The complexity of separability for semilinear sets and Parikh automata
<|reference_start|>The complexity of separability for semilinear sets and Parikh automata: In a separability problem, we are given two sets $K$ and $L$ from a class $\mathcal{C}$, and we want to decide whether there exists a set $S$ from a class $\mathcal{S}$ such that $K\subseteq S$ and $S\cap L=\emptyset$. In this case, we speak of separability of sets in $\mathcal{C}$ by sets in $\mathcal{S}$.   We study two types of separability problems. First, we consider separability of semilinear sets by recognizable sets of vectors (equivalently, by sets definable by quantifier-free monadic Presburger formulas). 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 $\Sigma^*\times\mathbb{N}^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.<|reference_end|>
@article{collins2024the,
    title={The complexity of separability for semilinear sets and Parikh automata},
    author={Elias Rojas Collins, Chris K"ocher, Georg Zetzsche},
    journal={arXiv preprint arXiv:2410.00548},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.00548},
    primaryClass={cs.FL}
}