Detecting palindromes, patterns, and borders in regular languages

Terry Anderson, John Loftus, Narad Rampersad +2

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…