Treatment of epsilon moves in subset construction

G van Noord*

*Bijbehorende auteur voor dit werk

    OnderzoeksoutputAcademicpeer review

    19 Citaten (Scopus)
    211 Downloads (Pure)


    The paper discusses the problem of determinizing finite-state automata containing large numbers of E-moves. Experiments with finite-state approximations of natural language grammars often give vise to very large automata with a very large number of E-moves. The paper identifies and compares a number of subset construction algorithms that treat E-moves. Experiments have been performed which indicate that the algorithms differ considerably in practice, both with respect to the size of the resulting deterministic automaton, and with respect to practical efficiency Furthermore, the experiments suggest that the average number of E-moves per state can be used to predict which algorithm is likely to be the fastest for a given input automaton.

    Originele taal-2English
    Pagina's (van-tot)61-76
    Aantal pagina's16
    TijdschriftComputational Linguistics
    Nummer van het tijdschrift1
    StatusPublished - mrt-2000

    Citeer dit