Minimization algorithms for sequential transducers

DOI10.1016/S0304-3975(98)00115-7zbMath0944.68091MaRDI QIDQ1575676

Mehryar Mohri

Publication date: 21 August 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

finite automata; semiring; rational power series; finite-state transducers; shortest-paths algorithms

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines, Using Ranked Semirings for Representing Morphology Automata, Nondeterministic Moore Automata and Brzozowski’s Algorithm, FINITELY SUBSEQUENTIAL TRANSDUCERS, COVER TRANSDUCERS FOR FUNCTIONS WITH FINITE DOMAIN, Largest common prefix of a regular tree language, A coalgebraic perspective on linear weighted automata, Translating regular expression matching into transducers, Nondeterministic Moore automata and Brzozowski's minimization algorithm, An improved algorithm for determinization of weighted and fuzzy automata, Pattern expressions and pattern automata, Weighted finite automata over strong bimonoids, Determinization of weighted finite automata over strong bimonoids, Deciding equivalence of top-down XML transformations in polynomial time, Minimizing deterministic weighted tree automata, The suffix tree of a tree and minimizing sequential transducers, Deterministic generalized automata, A proof of Choffrut's theorem on subsequential functions, Finite-state transducer cascades to extract named entities in texts., Minimization algorithms for sequential transducers, Pseudo-minimal transducer, The design principles of a weighted finite-state transducer library, Determinization of transducers over finite and infinite words., Minimizing subsequential transducers: a survey., Conditions for the existence of maximal factorizations, Computing the prefix of an automaton, EARLIEST NORMAL FORM AND MINIMIZATION FOR BOTTOM-UP TREE TRANSDUCERS, WEIGHTED NESTED WORD AUTOMATA AND LOGICS OVER STRONG BIMONOIDS, OpenFst: A General and Efficient Weighted Finite-State Transducer Library, Reducing Acyclic Cover Transducers, Minimizing Deterministic Weighted Tree Automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Deterministic synchronization of automata with bounded delay
• The suffix tree of a tree and minimizing sequential transducers
• Sur une variante des fonctions séquentielles
• Une caractérisation des fonctions séquentielles et des fonctions sous- séquentielles en tant que rélations rationnelles
• Minimization algorithms for sequential transducers
• Economy of description for single-valued transducers
• On the computational power of pushdown automata
• On a routing problem
• Faster algorithms for the shortest path problem
• Minimization of Rational Word Functions
• Finding Dominators in Directed Graphs
• Fibonacci heaps and their uses in improved network optimization algorithms
• On Relations Defined by Generalized Finite Automata
• Depth-First Search and Linear Graph Algorithms
• A Theorem on Boolean Matrices