کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6873880 | 1440709 | 2018 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the computational complexity of problems related to distinguishability sets
ترجمه فارسی عنوان
در پیچیدگی محاسباتی مشکلات مربوط به مجموعه های تمایز
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
ویژگی های مشخصه، هماهنگ سازی، پیچیدگی محاسباتی، پیچیدگی دولت، اتوماتای محدود تعیین کننده،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We study the computational complexity of problems related to distinguishability sets for regular languages. Roughly speaking, the distinguishability set D(L) for a (not necessarily regular) language L consists of all those words w for which there exists x and y such that word xw is in L if and only if word yx is not in L; hence the word w distinguishes the two prefixes x and y. One can view this mapping from L to its distinguishability set as an operator D:2Σââ2Σâ with Lâ¦D(L). In particular, we investigate the complexity of the representation problem, i.e., deciding for two given automata A and B, whether B accepts the distinguishability set of L(A). It is shown that this problem and some of its variants are highly intractable, namely PSPACE-complete. In fact, determining the size of an automaton for D(L(A)) is already PSPACE-complete. On the other hand, questions related to the hierarchy induced by iterated application of the D-operator turn out to be much easier. For instance, the question whether for a given automaton A, the accepted language is equal to its own distinguishability set, i.e., whether L(A)=D(L(A)) holds, is shown to be NL-complete. As a byproduct of our investigations, we found a nice characterization of synchronizing automata, namely that a (minimal) automaton A is synchronizing if and only if D(L(A))=D2(L(A)).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 259, Part 2, April 2018, Pages 225-236
Journal: Information and Computation - Volume 259, Part 2, April 2018, Pages 225-236
نویسندگان
Markus Holzer, Sebastian Jakobi,