Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
From MaRDI portal
Publication:4210084
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
(35)- Converting finite width AFAs to nondeterministic and universal finite automata
- Deciding path size of nondeterministic (and input-driven) pushdown automata
- Ambiguity of unary symmetric difference NFAs
- Ambiguity and communication
- Left is Better Than Right for Reducing Nondeterminism of NFAs
- The size of power automata.
- More on deterministic and nondeterministic finite cover automata (extended abstract)
- A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata
- Operations on Unambiguous Finite Automata
- Unambiguous finite automata over a unary alphabet
- Ambiguity and structural ambiguity of symmetric difference NFAs
- DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
- Lower bounds for the transition complexity of NFAs
- Branching measures and nearly acyclic NFAs
- Worst Case Branching and Other Measures of Nondeterminism
- Descriptional complexity of unambiguous input-driven pushdown automata
- More on deterministic and nondeterministic finite cover automata
- Operations on Unambiguous Finite Automata
- Nondeterministic biautomata and their descriptional complexity
- Communication complexity method for measuring nondeterminism in finite automata
- On the difference set of two transductions
- Descriptional complexity of finite automata -- selected highlights
- Structural properties of NFAs and growth rates of nondeterminism measures
- Operational state complexity of unary NFAs with finite nondeterminism
- In memoriam Chandra Kintala
- Complexity of exclusive nondeterministic finite automata
- Tight lower bounds on the size of sweeping automata
- From finite automata to regular expressions and back -- a summary on descriptional complexity
- Existential and universal width of alternating finite automata
- Computing the width of non-deterministic automata
- Unambiguity in automata theory
- SOFSEM 2006: Theory and Practice of Computer Science
- On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
- On the state complexity of closures and interiors of regular languages with subwords and superwords
- Width measures of alternating finite automata
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)
