2004/08/10 by Wojciech Skut, Skut, Wojciech
Computer Science · #Algorithms and Data Compression #Computation and Language (cs.CL) #Data Structures and Algorithms (cs.DS) #F.4.3 #FOS: Computer and information sciences #Machine Learning and Algorithms #cs.CL #cs.DS #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.cs/0408026
Proceedings of COLING 2004 (to appear), 7 pages, 5 figures
arxiv created 2004/08/10 · openalex publication_date 2004/08/10 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper presents an efficient algorithm for the incremental construction of a minimal acyclic sequential transducer (ST) for a dictionary consisting of a list of input and output strings. The algorithm generalises a known method of constructing minimal finite-state automata (Daciuk et al. 2000). Unlike the algorithm published by Mihov and Maurel (2001), it does not require the input strings to be sorted. The new method is illustrated by an application to pronunciation dictionaries.