TY - GEN
T1 - Minimization of sequential transducers
AU - Mohri, Mehryar
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1994.
PY - 1994
Y1 - 1994
N2 - We present an algorithm for minimizing sequential transducers. This algorithm is shown to be efficient, since in the case of acyclic transducers it operates in O(|E| + |V| + (E | - |V| + |F|) (|Pmax| + 1) steps, where E is the set of edges of the given transducer, V the set of its vertices, F the set of final states, and Pmax the longest of the greatest common prefixes of the output paths leaving each state of the transducer. It can be applied to a larger class of transducers which includes subsequential transducers.
AB - We present an algorithm for minimizing sequential transducers. This algorithm is shown to be efficient, since in the case of acyclic transducers it operates in O(|E| + |V| + (E | - |V| + |F|) (|Pmax| + 1) steps, where E is the set of edges of the given transducer, V the set of its vertices, F the set of final states, and Pmax the longest of the greatest common prefixes of the output paths leaving each state of the transducer. It can be applied to a larger class of transducers which includes subsequential transducers.
UR - http://www.scopus.com/inward/record.url?scp=85026734155&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85026734155&partnerID=8YFLogxK
U2 - 10.1007/3-540-58094-8_14
DO - 10.1007/3-540-58094-8_14
M3 - Conference contribution
AN - SCOPUS:85026734155
SN - 9783540580942
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 151
EP - 163
BT - Combinatorial Pattern Matching - 5th Annual Symposium, CPM 1994, Proceedings
A2 - Crochemore, Maxime
A2 - Gusfield, Dan
PB - Springer Verlag
T2 - 5th Annual Symposium on Combinatorial Pattern Matching, CPM 1994
Y2 - 5 June 1994 through 8 June 1994
ER -