GENERAL ALGORITHMS FOR TESTING THE AMBIGUITY OF FINITE AUTOMATA AND THE DOUBLE-TAPE AMBIGUITY OF FINITE-STATE TRANSDUCERS

DOI10.1142/S0129054111008477zbMath1216.68139MaRDI QIDQ3016223

Cyril Allauzen, Ashish Rastogi, Mehryar Mohri

Publication date: 14 July 2011

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

A Disambiguation Algorithm for Finite Automata and Functional Transducers ⋮ A FILTER-BASED ALGORITHM FOR EFFICIENT COMPOSITION OF FINITE-STATE TRANSDUCERS ⋮ ON THE DISAMBIGUATION OF FINITE AUTOMATA AND FUNCTIONAL TRANSDUCERS ⋮ Operations on Unambiguous Finite Automata ⋮ Solving string problems on graphs using the labeled direct product ⋮ A Pattern Logic for Automata with Outputs

Cites Work

• On the finite-valuedness problem for sequential machines
• On the degree of ambiguity of finite automata
• On finite semigroups of matrices
• Un algorithme calculant le cardinal, fini ou infini, des demi-groupes de matrices
• Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
• ON THE COMPUTATION OF THE RELATIVE ENTROPY OF PROBABILISTIC AUTOMATA
• EDIT-DISTANCE OF WEIGHTED AUTOMATA: GENERAL DEFINITIONS AND ALGORITHMS
• A variant of a recursively unsolvable problem

This page was built for publication: GENERAL ALGORITHMS FOR TESTING THE AMBIGUITY OF FINITE AUTOMATA AND THE DOUBLE-TAPE AMBIGUITY OF FINITE-STATE TRANSDUCERS