On the degree of ambiguity of finite automata
From MaRDI portal
Publication:1177168
DOI10.1016/0304-3975(91)90381-BzbMath0738.68059WikidataQ126376694 ScholiaQ126376694MaRDI QIDQ1177168
Publication date: 26 June 1992
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items (45)
Polynomially ambiguous probabilistic automata on restricted languages ⋮ Equivalence of finite-valued tree transducers is decidable ⋮ When are emptiness and containment decidable for probabilistic automata? ⋮ Width of Non-deterministic Automata ⋮ Polynomially ambiguous unary weighted automata over fields ⋮ Distance automata having large finite distance or finite ambiguity ⋮ Unnamed Item ⋮ Existential and universal width of alternating finite automata ⋮ Ambiguity, weakness, and regularity in probabilistic Büchi automata ⋮ Operations on Unambiguous Finite Automata ⋮ Copyless cost-register automata: structure, expressiveness, and closure properties ⋮ Joint Spectral Radius Theory for Automated Complexity Analysis of Rewrite Systems ⋮ GENERAL ALGORITHMS FOR TESTING THE AMBIGUITY OF FINITE AUTOMATA AND THE DOUBLE-TAPE AMBIGUITY OF FINITE-STATE TRANSDUCERS ⋮ Single-valuedness of tree transducers is decidable in polynomial time ⋮ Ambiguity and communication ⋮ Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton ⋮ Sequential? ⋮ Unnamed Item ⋮ On finitely generated monoids of matrices with entries in $\mathbb {N}$ ⋮ Component simulation-based substitutivity managing QoS and composition issues ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Branching Measures and Nearly Acyclic NFAs ⋮ Finite sequentiality of unambiguous max-plus tree automata ⋮ On degrees of ambiguity for Büchi tree automata ⋮ Operations on Unambiguous Finite Automata ⋮ On Finite and Polynomial Ambiguity of Weighted Tree Automata ⋮ Register Transducers Are Marble Transducers ⋮ Decidability of Cutpoint Isolation for Probabilistic Finite Automata on Letter-Bounded Inputs. ⋮ Origin-equivalence of two-way word transducers is in PSPACE ⋮ Polynomially Ambiguous Probabilistic Automata on Restricted Languages ⋮ Probabilistic automata of bounded ambiguity ⋮ Max-plus automata ⋮ Probabilistic Automata of Bounded Ambiguity ⋮ Solving string problems on graphs using the labeled direct product ⋮ Unnamed Item ⋮ Width measures of alternating finite automata ⋮ Image-binary automata ⋮ Finite ambiguity and finite sequentiality in weighted automata over fields ⋮ Deciding path size of nondeterministic (and input-driven) pushdown automata ⋮ Weak Cost Register Automata are Still Powerful ⋮ A Pattern Logic for Automata with Outputs ⋮ A robust class of linear recurrence sequences ⋮ Structural properties of NFAs and growth rates of nondeterminism measures ⋮ Memoized regular expressions
Cites Work
- On the valuedness of finite transducers
- Amounts of nondeterminism in finite automata
- On the finite-valuedness problem for sequential machines
- The Burnside problem for semigroups
- On finite semigroups of matrices
- Un algorithme calculant le cardinal, fini ou infini, des demi-groupes de matrices
- On the finite degree of ambiguity of finite tree automata
- Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
- Deciding Equivalence of Finite Tree Automata
- On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
- Automata that recognize intersections of free submonoids
- Propriétés arithmétiques de séries rationnelles et ensembles denses
- On finitely generated monoids of matrices with entries in $\mathbb {N}$
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: On the degree of ambiguity of finite automata
