کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
429181 687076 2008 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Description and analysis of a bottom-up DFA minimization algorithm
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Description and analysis of a bottom-up DFA minimization algorithm
چکیده انگلیسی

We establish linear-time reductions between the minimization of a deterministic finite automaton (DFA) and the conjunction of 3 subproblems: the minimization of a strongly connected DFA, the isomorphism problem for a set of strongly connected minimized DFAs, and the minimization of a connected DFA consisting in two strongly connected components, both of which are minimized. We apply this procedure to minimize, in linear time, automata whose nontrivial strongly connected components are cycles.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 107, Issue 2, 16 July 2008, Pages 52-59