A new recursive incremental algorithm for building minimal acyclic deterministic finite automata

B.W. Watson

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

Abstract

This chapter presents a new algorithm for incrementally building minimal acyclic deterministic finite automata. Such minimal automata are a compact representation of a finite set of words (e.g. in a spell checker). The incremental aspect of such algorithms (where the intermediate automaton is minimal) facilitates the construction of very large automata in limited computer memory where other (nonincremental) algorithms would fail with intermediate data structures too large to fit in memory.
Original languageEnglish
Title of host publicationGrammars and automata for string processes : from mathematics and computer science to biology, and back : essays in honour of Gheorghe Paun
EditorsC. Martin-Vide, V. Mitrana
PublisherTaylor and Francis Ltd.
Pages189-
ISBN (Print)0-415-29885-7
DOIs
Publication statusPublished - 2003

Publication series

NameTopics in Computer Mathematics
Volume9
ISSN (Print)0275-5815

Fingerprint

Dive into the research topics of 'A new recursive incremental algorithm for building minimal acyclic deterministic finite automata'. Together they form a unique fingerprint.

Cite this