Detecting palindromes, patterns, and borders in regular languages

Autor:	Anderson, Terry, Loftus, John, Rampersad, Narad, Santean, Nicolae, Shallit, Jeffrey
Rok vydání:	2007
Předmět:	Computer Science - Computational Complexity Computer Science - Discrete Mathematics Computer Science - Formal Languages and Automata Theory F.4.3
Druh dokumentu:	Working Paper
Popis:	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. Comment: Full version of a paper submitted to LATA 2008. This is a new version with John Loftus added as a co-author and containing new results on unbordered words
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/0711.3183 Zobrazit plný text záznamu View this record from Arxiv