Työväentutkimus Vuosikirja · 2004 · 25 citations · 19 references
Open access
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsDiscrete MathematicsAutomata TheoryFinite AutomataFinite-state MachinesAutomata MinimizationConditionsDeterministic Finite AutomataDfa MinimizationFinite Automata TheoryLanguage ReversalNondeterministic Finite AutomataReversal Language
In this thesis, we consider minimality and size reduction issues of one-tape and multitape automata. Although the topic of minimization of one-tape automata has been widely studied for many years, it seems that some issues have not gained attention. One of these issues concerns finding specific conditions on automata that imply their minimality in the class of nondeterministic finite automata (NFA) accepting the same language. Using the theory of NFA minimization developed by Kameda and Weiner in 1970, we show that any bideterministic automaton (that is, a deterministic automaton with its reversal also being deterministic) is a unique minimal automaton among all NFA accepting its language. In addition to the minimality in regard to the number of states, we also show its minimality in the number of transitions. Using the same theory of Kameda and Weiner, we also obtain a more general minimality result. We specify a set of sufficient conditions under which a minimal deterministic automaton (DFA)
19
Finite Automata and Their Decision Problems
M. O. Rabin, D. Scott · IBM Journal of Research and Development · 1959 · 1.9K citations
Inference of Reversible Languages
Dana Angluin · Journal of the ACM · 1982 · 534 citations · Full text
Tao Jiang, Bala Ravikumar · SIAM Journal on Computing · 1993 · 249 citations