Detecting palindromes, patterns, and borders in regular languages
| dc.creator | Anderson, Terry | |
| dc.creator | Loftus, John | |
| dc.creator | Rampersad, Narad | |
| dc.creator | Santean, Nicolae | |
| dc.creator | Shallit, Jeffrey | |
| dc.date | 2007-11-20 | |
| dc.date | 2008-06-09 | |
| dc.date.accessioned | 2026-07-07T13:02:56Z | |
| dc.date.available | 2026-07-07T13:02:56Z | |
| dc.description | 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. | |
| dc.description | 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 | |
| dc.identifier | https://arxiv.org/abs/0711.3183 | |
| dc.identifier | http://arxiv.org/abs/0711.3183 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/226619 | |
| dc.subject | Computational Complexity | |
| dc.subject | Discrete Mathematics | |
| dc.subject | Formal Languages and Automata Theory | |
| dc.subject | F.4.3 | |
| dc.title | Detecting palindromes, patterns, and borders in regular languages | |
| dc.type | text |