کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4951154 | 1441195 | 2017 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Deciding definability by deterministic regular expressions
ترجمه فارسی عنوان
تصمیمگیابی با تعریف منظم
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
عبارات منظم، تعیین کننده، تعریف، پیچیدگی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We investigate the complexity of deciding whether a given regular language can be expressed by a deterministic regular expression. Our main technical result shows that deciding if the language of a given regular expression (or, non-deterministic finite automaton) can be defined by a deterministic regular expression is PSPACE-complete. The problem becomes EXPSPACE-complete if the input language is represented as a regular expression with counters and NL-hard if the input language is given by a minimal deterministic finite automaton.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 88, September 2017, Pages 75-89
Journal: Journal of Computer and System Sciences - Volume 88, September 2017, Pages 75-89
نویسندگان
Wojciech CzerwiÅski, Claire David, Katja Losemann, Wim Martens,