Home > Table of Contents


Proceedings of 2009 International Workshop on Information Security and Application (IWISA 2009)

Qingdao, China, November 21-22, 2009

Editors: Feng Gao and Xijun Zhu

AP Catalog Number: AP-PROC-CS-09CN004

ISBN: 978-952-5726-06-0

Page(s): 417-420

An Algorithm for Minimizing a Completely Deterministic Finite Automaton Based on State Transition Inverse Mapping

Chu Chen, Pinghong Ren, Jiguo Yu, and Nong Yu

Full text: PDF


During the process of minimizing a deterministic finite automaton, there exist computing dependency and repetitive computing problems caused by the disorder of selecting a set to partition in the partition algorithm or by the disorder of computing state-pairs in the combination algorithm. To solve theses problems, a new algorithm for minimizing a completely deterministic finite automaton is presented. Firstly, based on the concept of a completely deterministic finite automaton, characteristics of state transition inverse mapping and the usage to reduce repetitive computing are analyzed. Secondly, the algorithm for minimizing a completely deterministic finite automaton, its rightness proof and analysis of time complexity are given. In the end, an experiment is carried out and the result shows that this algorithm is fairly efficient for minimizing a finite automaton.

Index Terms

minimizing, completely deterministic, finite automaton, state transition, inverse mapping

Copyright @ 2009 ACADEMY PUBLISHER All rights reserved