Incremental construction of minimal acyclic finite-state automata

• DOI: 10.48550/arxiv.cs/0007009
• Publication Date: 2000-01-01
• Authors: Jan Daciuk; Stoyan Mihov; Bruce W. Watson; Richard A. Watson
• Keywords: FOS: Computer and information sciences; Computer Science - Computation and Language; I.2.7; Computational linguistics. Natural language processing; 0202 electrical engineering, electronic engineering, information engineering; 02 engineering and technology; P98-98.5; Computation and Language (cs.CL)

In this paper, we describe a new method for constructing minimal, deterministic, acyclic finite-state automata from set of strings. Traditional methods consist two phases: the first to construct trie, second one minimize it. Our approach is minimal automaton in single phase by adding strings and minimizing resulting on-the-fly. We present general algorithm as well specialization that relies upon lexicographical ordering input