On the disambiguation of weighted automata

DOI10.1007/978-3-319-22360-5_22MaRDI QIDQ2947428zbMATH OpenOpenAlexFDO

Authors Mehryar Mohri, Michael D. Riley

Publication date 23 September 2015

Published in Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.0500

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Natural language processing (68T50)

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.

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

• scientific article; zbMATH DE number 3932372 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 2040319 (Why is no real title available?)
• A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata
• Biological Sequence Analysis
• Decidability, undecidability, and PSPACE-completeness of the twins property in the tropical semiring
• Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton
• Deciding unambiguity and sequentiality of polynomially ambiguous min-plus automata
• Digital image compression
• Finding the k Shortest Paths
• 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)