Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
From MaRDI portal
Publication:4210084
DOI10.1137/S0097539793252092zbMATH Open0911.68144OpenAlexW2079577017MaRDI QIDQ4210084FDOQ4210084
Authors: Hing-Man Leung 
Publication date: 20 September 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539793252092
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)
- Deciding path size of nondeterministic (and input-driven) pushdown automata
- Ambiguity of unary symmetric difference NFAs
- Left is Better Than Right for Reducing Nondeterminism of NFAs
- Ambiguity and communication
- The size of power automata.
- A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata
- More on deterministic and nondeterministic finite cover automata (extended abstract)
- Operations on Unambiguous Finite Automata
- Unambiguous finite automata over a unary alphabet
- DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
- Ambiguity and structural ambiguity of symmetric difference NFAs
- Lower bounds for the transition complexity of NFAs
- Branching measures and nearly acyclic NFAs
- Worst Case Branching and Other Measures of Nondeterminism
- More on deterministic and nondeterministic finite cover automata
- Descriptional complexity of unambiguous input-driven pushdown automata
- Operations on Unambiguous Finite Automata
- Nondeterministic biautomata and their descriptional complexity
- On the difference set of two transductions
- Descriptional complexity of finite automata -- selected highlights
- Communication complexity method for measuring nondeterminism in finite automata
- Structural properties of NFAs and growth rates of nondeterminism measures
- In memoriam Chandra Kintala
- Operational state complexity of unary NFAs with finite nondeterminism
- 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
- Converting finite width AFAs to nondeterministic and universal 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)
