کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
426423 | 686058 | 2015 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Prime languages
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We say that a deterministic finite automaton (DFA) AA is composite if there are DFAs A1,…,AtA1,…,At such that L(A)=⋂i=1tL(Ai) and the index of every AiAi is strictly smaller than the index of AA. Otherwise, AA is prime.We study the problem of deciding whether a given DFA is composite, the number of DFAs required in a decomposition, decompositions that are based on abstractions, methods to prove primality, and structural properties of DFAs that make the problem simpler or are retained in a decomposition. We also provide an algebraic view of the problem and demonstrate its usefulness for the special case of permutation DFAs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 240, February 2015, Pages 90–107
Journal: Information and Computation - Volume 240, February 2015, Pages 90–107
نویسندگان
Orna Kupferman, Jonathan Mosheiff,