2007/11/20 by Terry Anderson, Anderson, Terry, John A. Loftus +7
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Computational Complexity (cs.CC) #DNA and Biological Computing #Discrete Mathematics (cs.DM) #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.0711.3183
openalex publication_date 2007/11/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a language L and a nondeterministic finite automaton M, we consider whether we can determine efficiently (in the size of M) if M accepts at least one word in L, or infinitely many words. Given that M accepts at least one word in L, we consider how long a shortest word can be. The languages L that we examine include the palindromes, the non-palindromes, the k-powers, the non-k-powers, the powers, the non-powers (also called primitive words), the words matching a general pattern, the bordered words, and the unbordered words.