Detecting palindromes, patterns, and borders in regular languages

Details Detecting palindromes, patterns, and borders in regular languages Detecting palindromes, patterns, and borders in regular languages

2007-11-20

arxiv.org/abs/0711.3183v2

Computer Science

Computational Complexity

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

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Detecting palindromes, patterns, and borders in regular languages does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Detecting palindromes, patterns, and borders in regular languages, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Detecting palindromes, patterns, and borders in regular languages will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-392141