کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4952043 1442007 2017 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On Boolean combinations forming piecewise testable languages
ترجمه فارسی عنوان
در ترکیب بولی تشکیل زبان های قابل تست
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
نویسندگان
, ,