کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
392468 | 664772 | 2016 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A sufficient condition to polynomially compute a minimum separating DFA
ترجمه فارسی عنوان
شرط کافی برای محاسبه چندجمله ای DFA جداسازی حداقل
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
DFA جداسازی حداقل ؛ DFA سازگار حداقل ؛ چک کردن مدل؛ به حداقل رساندن اتوماتیک ناقص تعیین شده
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
هوش مصنوعی
چکیده انگلیسی
The computation of a minimal separating automaton (MSA) for regular languages has been studied from many different points of view, from synthesis of automata or Grammatical Inference to the minimization of incompletely specified machines or Compositional Verification. In the general case, the problem is NP-complete, but this drawback does not prevent the problem from having a real application in the above-mentioned fields. In this paper, we propose a sufficient condition that guarantees that the computation of the MSA can be carried out with polynomial time complexity.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Sciences - Volumes 370–371, 20 November 2016, Pages 204–220
Journal: Information Sciences - Volumes 370–371, 20 November 2016, Pages 204–220
نویسندگان
Manuel Vázquez de Parga, Pedro García, Damián López,