1999/10/25 by Mark-Jan Nederhof, Nederhof, Mark-Jan · 2 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Computation and Language (cs.CL) #DNA and Biological Computing #F.1.1 #F.4.3 #FOS: Computer and information sciences #cs.CL #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.cs/9910022
28 pages. To appear in Computational Linguistics 26(1), March 2000
arxiv created 1999/10/25 · openalex publication_date 1999/10/25 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Several methods are discussed that construct a finite automaton given a context-free grammar, including both methods that lead to subsets and those that lead to supersets of the original context-free language. Some of these methods of regular approximation are new, and some others are presented here in a more refined form with respect to existing literature. Practical experiments with the different methods of regular approximation are performed for spoken-language input: hypotheses from a speech recognizer are filtered through a finite automaton.