Portal de Periódicos da CAPES

Detecting palindromes, patterns and borders in regular languages

2009; Elsevier BV; Volume: 207; Issue: 11 Linguagem: Inglês

10.1016/j.ic.2008.06.007

1090-2651

Terry Anderson, John A. Loftus, Narad Rampersad, Nicolae Sântean, Jeffrey Shallit,

Coding theory and cryptography

Given a language L and a non-deterministic 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.