کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952043 | 1442007 | 2017 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On Boolean combinations forming piecewise testable languages
ترجمه فارسی عنوان
در ترکیب بولی تشکیل زبان های قابل تست
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A regular language is k-piecewise testable (k-PT) if it is a Boolean combination of languages of the form La1a2â¦an=Σâa1Σâa2Σââ¯Î£âanΣâ, where aiâΣ and 0â¤nâ¤k. Given a finite automaton A, if the language L(A) is piecewise testable, we want to express it as a Boolean combination of languages of the above form. The idea is as follows. If the language is k-PT, then there exists a congruence â¼k of finite index such that L(A) is a finite union of â¼k-classes. Every such class is characterized by an intersection of languages of the from Lu, for |u|â¤k, and their complements. To represent the â¼k-classes, we make use of the â¼k-canonical DFA. We identify the states of the â¼k-canonical DFA whose union forms the language L(A) and use them to construct the required Boolean combination. We study the computational and descriptional complexity of related problems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 682, 19 June 2017, Pages 165-179
Journal: Theoretical Computer Science - Volume 682, 19 June 2017, Pages 165-179
نویسندگان
TomáÅ¡ Masopust, Michaël Thomazo,