کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10330775 | 686132 | 2011 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Decision problems for convex languages
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We examine decision problems for various classes of convex languages, previously studied by Ang and Brzozowski, originally under the name “continuous languages”. We can decide whether a language L is prefix-, suffix-, factor-, or subword-convex in polynomial time if L is represented by a DFA, but these problems become PSPACE-complete if L is represented by an NFA. If a regular language is not convex, we find tight upper bounds on the length of the shortest words demonstrating this fact, in terms of the number of states of an accepting DFA. Similar results are proved for some subclasses of convex languages: the prefix-, suffix-, factor-, and subword-closed languages, and the prefix-, suffix-, factor-, and subword-free languages. Finally, we briefly examine these questions where L is represented by a context-free grammar.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 209, Issue 3, March 2011, Pages 353-367
Journal: Information and Computation - Volume 209, Issue 3, March 2011, Pages 353-367
نویسندگان
Janusz Brzozowski, Jeffrey Shallit, Zhi Xu,