Pith. sign in

REVIEW

Incremental construction of minimal acyclic finite-state automata

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv cs/0007009 v1 pith:PFYQQS4L submitted 2000-07-06 cs.CL

Jan Daciuk , Stoyan Mihov , Bruce Watson , Richard Watson This is my paper · ORCID
classification cs.CL
keywords minimalstringsacyclicautomataautomatonconstructfinite-stateadding
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

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 construct a trie, the second one to minimize it. Our approach is to construct a minimal automaton in a single phase by adding new strings one by one and minimizing the resulting automaton on-the-fly. We present a general algorithm as well as a specialization that relies upon the lexicographical ordering of the input strings.

Discussion (0). Continue with ORCID to comment.

Pith tools