کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419146 | 681747 | 2014 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Cycle-aware minimization of acyclic deterministic finite-state automata
ترجمه فارسی عنوان
به حداقل رساندن چرخه آشکارساز اتوماتیک حالت محدود به صورت آکسیلیک
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
کمینه سازی، خودکار اتوماتیک حالت قطعی، الگوریتمیک
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper a linear-time algorithm for the minimization of acyclic deterministic finite-state automata is presented. The algorithm runs significantly faster than previous algorithms for the same task. This is shown by a comparison of the running times of both algorithms. Additionally, a variation of the new algorithm is presented which handles cyclic automata as input. The new cycle-aware algorithm minimizes acyclic automata in the desired way. In case of cyclic input, the algorithm minimizes all acyclic suffixes of the input automaton.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 163, Part 3, 30 January 2014, Pages 238–246
Journal: Discrete Applied Mathematics - Volume 163, Part 3, 30 January 2014, Pages 238–246
نویسندگان
Johannes Bubenzer,