2019/02/17 by Philip Sieder, Sieder, Philip
Biochemistry, Genetics and Molecular Biology · Computer Science · #Coding theory and cryptography #DNA and Biological Computing #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #cs.FL #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1902.06253
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
arxiv created 2019/02/17 · openalex publication_date 2019/02/17 · arxiv updated 2019/02/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 NP - completeness of primality, but no actual bounds are given. Using techniques of Martens et al., we prove the NP lower bound and give a Π2P upper bound for deciding primality of finite languages given as deterministic finite automata.