کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
426856 686325 2009 23 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Detecting palindromes, patterns and borders in regular languages
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Detecting palindromes, patterns and borders in regular languages
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 207, Issue 11, November 2009, Pages 1096-1118