GENERAL ALGORITHMS FOR TESTING THE AMBIGUITY OF FINITE AUTOMATA AND THE DOUBLE-TAPE AMBIGUITY OF FINITE-STATE TRANSDUCERS
From MaRDI portal
Publication:3016223
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)
68W40: Analysis of algorithms
68Q45: Formal languages and automata
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
ON THE DISAMBIGUATION OF FINITE AUTOMATA AND FUNCTIONAL TRANSDUCERS, A Pattern Logic for Automata with Outputs, Solving string problems on graphs using the labeled direct product, Operations on Unambiguous Finite Automata, A Disambiguation Algorithm for Finite Automata and Functional Transducers, A FILTER-BASED ALGORITHM FOR EFFICIENT COMPOSITION OF FINITE-STATE TRANSDUCERS
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
