کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6873969 | 686072 | 2015 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Deciding determinism of unary languages
ترجمه فارسی عنوان
تصمیم گیری جبریانه زبان های اناری
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper, we investigate the complexity of deciding determinism of unary languages. First, we give a method to derive a set of arithmetic progressions from a regular expression E over a unary alphabet, and establish relations between numbers represented by these arithmetic progressions and words in L(E). Next, we define a problem relating to arithmetic progressions and investigate the complexity of this problem. Then by a reduction from this problem we show that deciding determinism of unary languages is coNP-complete. Finally, we extend our derivation method to expressions with counting, and prove that deciding whether an expression over a unary alphabet with counting defines a deterministic language is in Î 2p. We also establish a tight upper bound for the size of the minimal DFA for expressions with counting.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 245, December 2015, Pages 181-196
Journal: Information and Computation - Volume 245, December 2015, Pages 181-196
نویسندگان
Ping Lu, Feifei Peng, Haiming Chen, Lixiao Zheng,