Structural properties of NFAs and growth rates of nondeterminism measures
From MaRDI portal
Publication:2113384
DOI10.1016/j.ic.2021.104690OpenAlexW3120287019MaRDI QIDQ2113384
Publication date: 14 March 2022
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2021.104690
Related Items (3)
Converting finite width AFAs to nondeterministic and universal finite automata ⋮ Existential and universal width of alternating finite automata ⋮ Deciding path size of nondeterministic (and input-driven) pushdown automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Descriptional and computational complexity of finite automata -- a survey
- Cycle height of finite automata
- On measuring nondeterminism in regular languages
- On the degree of ambiguity of finite automata
- Communication complexity method for measuring nondeterminism in finite automata
- Nondeterminism growth and state complexity
- Branching measures and nearly acyclic NFAs
- From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity
- Comparisons between Measures of Nondeterminism on Finite Automata
- Parameterized Prefix Distance between Regular Languages
- Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
- Faster algorithms for the shortest path problem
- FINDING THE GROWTH RATE OF A REGULAR OR CONTEXT-FREE LANGUAGE IN POLYNOMIAL TIME
- Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
- Characterizing regular languages with polynomial densities
- State Complexity of Finite Tree Width NFAs
- Ambiguity, Nondeterminism and State Complexity of Finite Automata
- Depth-First Search and Linear Graph Algorithms
- DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
This page was built for publication: Structural properties of NFAs and growth rates of nondeterminism measures
