On the disambiguation of weighted automata
From MaRDI portal
Publication:2947428
DOI10.1007/978-3-319-22360-5_22zbMATH Open1465.68164arXiv1405.0500OpenAlexW2293090312MaRDI QIDQ2947428FDOQ2947428
Authors: Mehryar Mohri, Michael D. Riley 
Publication date: 23 September 2015
Published in: Implementation and Application of Automata (Search for Journal in Brave)
Abstract: We present a disambiguation algorithm for weighted automata. The algorithm admits two main stages: a pre-disambiguation stage followed by a transition removal stage. We give a detailed description of the algorithm and the proof of its correctness. The algorithm is not applicable to all weighted automata but we prove sufficient conditions for its applicability in the case of the tropical semiring by introducing the *weak twins property*. In particular, the algorithm can be used with all acyclic weighted automata, relevant to applications. While disambiguation can sometimes be achieved using determinization, our disambiguation algorithm in some cases can return a result that is exponentially smaller than any equivalent deterministic automaton. We also present some empirical evidence of the space benefits of disambiguation over determinization in speech recognition and machine translation applications.
Full work available at URL: https://arxiv.org/abs/1405.0500
Recommendations
- A disambiguation algorithm for weighted automata
- A disambiguation algorithm for finite automata and functional transducers
- ON THE DISAMBIGUATION OF FINITE AUTOMATA AND FUNCTIONAL TRANSDUCERS
- An optimal pre-determinization algorithm for weighted transducers
- Minimal-determinization of weighted automaton
Cites Work
- Biological Sequence Analysis
- Finding the k Shortest Paths
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata
- Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton
- Title not available (Why is that?)
- Deciding unambiguity and sequentiality of polynomially ambiguous min-plus automata
- Digital image compression
- Decidability, undecidability, and PSPACE-completeness of the twins property in the tropical semiring
- ON THE DISAMBIGUATION OF FINITE AUTOMATA AND FUNCTIONAL TRANSDUCERS
- On the disambiguation of weighted automata
Cited In (6)
- ON THE DISAMBIGUATION OF FINITE AUTOMATA AND FUNCTIONAL TRANSDUCERS
- A disambiguation algorithm for finite automata and functional transducers
- A disambiguation algorithm for weighted automata
- On deterministic weighted automata
- On the disambiguation of weighted automata
- Disambiguation of weighted tree automata
This page was built for publication: On the disambiguation of weighted automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947428)
