@inproceedings{6a83f9ad6cc340179f670fe7df98443d,
title = "Generic ε-removal algorithm for weighted automata",
abstract = "We present a new generic ε -removal algorithm for weighted automata and transducers defied over a semiring. The algorithm can be used with any semiring covered by our framework and works with any queue discipline adopted. It can be used in particular in the case of unweighted automata and transducers and weighted automata and transducers defined over the tropical semiring. It is based on a general shortest-distance algorithm that we briefly describe. We give a full description of the algorithm including its pseudocode and its running time complexity, discuss the more efficient case of acyclic automata, an on-the-fly implementation of the algorithm and an approximation algorithm in the case of the semirings not covered by our framework. We also illus-trate the use of the algorithm with several semirings.",
author = "Mehryar Mohri",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2001.; 5th International Conference on Implementation and Application of Automata, CIAA 2000 ; Conference date: 24-07-2000 Through 25-07-2000",
year = "2001",
doi = "10.1007/3-540-44674-5_19",
language = "English (US)",
isbn = "3540424911",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "230--242",
editor = "Sheng Yu and Andrei Paun",
booktitle = "Implementation and Application of Automata - 5th International Conference, CIAA 2000, Revised Papers",
}