DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
From MaRDI portal
Publication:5704377
DOI10.1142/S0129054105003418zbMath1090.68059OpenAlexW2093294649WikidataQ57380747 ScholiaQ57380747MaRDI QIDQ5704377
Publication date: 14 November 2005
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0129054105003418
Related Items (32)
Descriptional Complexity of Input-Driven Pushdown Automata ⋮ Unnamed Item ⋮ IN MEMORIAM CHANDRA KINTALA ⋮ Width of Non-deterministic Automata ⋮ On the Determinization Blowup for Finite Automata Recognizing Equal-Length Languages ⋮ On the state complexity of closures and interiors of regular languages with subwords and superwords ⋮ Operational state complexity of unary NFAs with finite nondeterminism ⋮ Left is Better Than Right for Reducing Nondeterminism of NFAs ⋮ Converting finite width AFAs to nondeterministic and universal finite automata ⋮ Unambiguous finite automata over a unary alphabet ⋮ Complexity of exclusive nondeterministic finite automata ⋮ On the transformation of two-way finite automata to unambiguous finite automata ⋮ Ambiguity and structural ambiguity of symmetric difference NFAs ⋮ Operations on Unambiguous Finite Automata ⋮ Descriptional complexity of unambiguous input-driven pushdown automata ⋮ A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton ⋮ On the transformation of two-way deterministic finite automata to unambiguous finite automata ⋮ Two-way unary automata versus logarithmic space ⋮ Lower bounds for the size of deterministic unranked tree automata ⋮ From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity ⋮ The \(k\)-distinct language: parameterized automata constructions ⋮ The containment problem for unambiguous register automata and unambiguous timed automata ⋮ On degrees of ambiguity for Büchi tree automata ⋮ Operations on Unambiguous Finite Automata ⋮ The Containment Problem for Unambiguous Register Automata ⋮ Ambiguity of Unary Symmetric Difference NFAs ⋮ Unambiguity in Automata Theory ⋮ Nondeterministic Tree Width of Regular Languages ⋮ Unnamed Item ⋮ Image-binary automata ⋮ Worst Case Branching and Other Measures of Nondeterminism ⋮ Structural properties of NFAs and growth rates of nondeterminism measures
Cites Work
- A lower bound technique for the size of nondeterministic finite automata
- Succinct representation of regular languages by Boolean automata
- Some remarks on multiple-entry finite automata
- Multiple-entry finite automata
- Communication complexity method for measuring nondeterminism in finite automata
- Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
- On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
- Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
This page was built for publication: DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
