Optimal Hyper-Minimization

Details Optimal Hyper-Minimization Optimal Hyper-Minimization

2011-04-15

arxiv.org/abs/1104.3007v1

Computer Science

Formal Languages and Automata Theory

15 pages, 5 figures

Scientific paper

Minimal deterministic finite automata (DFAs) can be reduced further at the expense of a finite number of errors. Recently, such minimization algorithms have been improved to run in time O(n log n), where n is the number of states of the input DFA, by [Gawrychowski and Je\.z: Hyper-minimisation made efficient. Proc. MFCS, LNCS 5734, 2009] and [Holzer and Maletti: An n log n algorithm for hyper-minimizing a (minimized) deterministic automaton. Theor. Comput. Sci. 411, 2010]. Both algorithms return a DFA that is as small as possible, while only committing a finite number of errors. These algorithms are further improved to return a DFA that commits the least number of errors at the expense of an increased (quadratic) run-time. This solves an open problem of [Badr, Geffert, and Shipman: Hyper-minimizing minimized deterministic finite state automata. RAIRO Theor. Inf. Appl. 43, 2009]. In addition, an experimental study on random automata is performed and the effects of the existing algorithms and the new algorithm are reported.

Affiliated with

Also associated with

No associations

Rating

Optimal Hyper-Minimization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimal Hyper-Minimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Hyper-Minimization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-8649