A Lower Bound for Primality of Finite Languages

Abstract

A regular language $L$ is said to be prime, if it is not the product of two non-trivial languages. Martens et al. settled the exact complexity of deciding primality for deterministic finite automata in 2010. For finite languages, Mateescu et al. and Wieczorek suspect the $\mathrm{NP}\text{ - }completeness$ of primality, but no actual bounds are given. Using techniques of Martens et al., we prove the $\mathrm{NP}$ lower bound and give a ${\Pi }_2^{\mathrm{P}}$ upper bound for deciding primality of finite languages given as deterministic finite automata.

18 pages; this paper is essentially my bachelor thesis submitted on 28th April 2017; we (Prof. Dr. Wim Martens, Dr. Matthias Niewerth, Johannes Doleschal and I) plan to release it as part of a more profound paper