The Levenshtein distance between two words is the minimal number of insertions, deletions
or substitutions that are needed to transform one word into the other. Levenshtein automata …

In this paper, we describe a new method for constructing minimal, deterministic, acyclic finite-
state automata from a set of strings. Traditional methods consist of two phases: the first to …

Finite-state methods are the most efficient mechanisms for analysing textual and symbolic
data, providing elegant solutions for an immense number of practical problems in …

We consider the problem of reducing the number of states of nondeterministic finite
automata, and show how to encode the reduction as a Boolean satisfiability problem. This …

Minimal acyclic deterministic finite automata (ADFAs) can be used as a compact
representation of finite string sets with fast access time. Creating them with traditional …

We present a semi-incremental algorithm for constructing minimal acyclic deterministic finite
automata. Such automata are useful for storing sets of words for spell-checking, among …

This thesis is submitted in partial fulfillment of the requirements for the degree of Doctor of
Philosophy (Ph. D) in the FASTAR group of the Department of Computer Science, University …

In this paper, we present a taxonomy of algorithms for constructing minimal acyclic
deterministic finite automata (MADFAs). Such automata represent finite languages and are …

This paper presents an algorithm for direct building of minimal acyclic subsequential
transducer, which represents a finite relation given as a sorted list of words with their …

This paper presents automaton construction algorithms based on the method for direct
building of minimal acyclic nite states automaton for a given list Mi98]. A detailed …