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 automatasemiringrational power seriesfinite-state transducersshortest-paths algorithms

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (31)

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

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

This page was built for publication: Minimization algorithms for sequential transducers