Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
From MaRDI portal
Recommendations
- Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
- SOFSEM 2006: Theory and Practice of Computer Science
- Descriptional complexity of ambiguity in symmetric difference NFAs
- scientific article; zbMATH DE number 4049114
- On the degree of ambiguity of finite automata
Cited in
(42)- The size of power automata.
- Tight lower bounds on the size of sweeping automata
- Communication complexity method for measuring nondeterminism in finite automata
- Width measures of alternating finite automata
- Deciding path size of nondeterministic (and input-driven) pushdown automata
- Structural properties of NFAs and growth rates of nondeterminism measures
- More on deterministic and nondeterministic finite cover automata
- Ambiguity and structural ambiguity of symmetric difference NFAs
- From finite automata to regular expressions and back -- a summary on descriptional complexity
- Operations on Unambiguous Finite Automata
- In memoriam Chandra Kintala
- More on deterministic and nondeterministic finite cover automata (extended abstract)
- Ambiguity of unary symmetric difference NFAs
- A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata
- On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
- Unambiguous finite automata over a unary alphabet
- Operations on Unambiguous Finite Automata
- Descriptional complexity of unambiguous input-driven pushdown automata
- Nondeterministic biautomata and their descriptional complexity
- Branching measures and nearly acyclic NFAs
- Computing the width of non-deterministic automata
- Worst Case Branching and Other Measures of Nondeterminism
- Ambiguity and communication
- Unambiguity in automata theory
- DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
- SOFSEM 2006: Theory and Practice of Computer Science
- Left is Better Than Right for Reducing Nondeterminism of NFAs
- Converting finite width AFAs to nondeterministic and universal finite automata
- Existential and universal width of alternating finite automata
- Complexity of exclusive nondeterministic finite automata
- On the difference set of two transductions
- Descriptional complexity of finite automata -- selected highlights
- From regular expressions to deterministic finite automata: \(2^{\frac{n}{2}+\sqrt{n}(\log n)^{\varTheta (1)}}\) states are necessary and sufficient
- On the transformation of two-way nondeterministic finite automata to unambiguous finite automata
- Existential and universal width of alternating finite automata
- Complexity of exclusive nondeterministic finite automata
- Complexity of unary exclusive nondeterministic finite automata
- Maximal universal width of an AFA is NP-hard
- Image-binary automata
- On the state complexity of closures and interiors of regular languages with subwords and superwords
- Operational state complexity of unary NFAs with finite nondeterminism
- Lower bounds for the transition complexity of NFAs
This page was built for publication: Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210084)
