On measuring nondeterminism in regular languages
From MaRDI portal
Publication:912641
DOI10.1016/0890-5401(90)90053-KzbMath0698.68068MaRDI QIDQ912641
Detlef Wotschke, Jonathan Goldstine, Chandra M. R. Kintala
Publication date: 1990
Published in: Information and Computation (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)
Related Items
Measures of nondeterminism for pushdown automata, Regulated nondeterminism in pushdown automata, The degree of word-expansion of lexicalized RRWW-automata - A new measure for the degree of nondeterminism of (context-free) languages, IN MEMORIAM CHANDRA KINTALA, On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata, Context-dependent nondeterminism for pushdown automata, On finite automata with limited nondeterminism (extended abstract), Pushdown automata with bounded nondeterminism and bounded ambiguity, Distance automata having large finite distance or finite ambiguity, Regulated Nondeterminism in Pushdown Automata, A Measure for the Degree of Nondeterminism of Context-Free Languages, 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, Existential and universal width of alternating finite automata, On the relation between ambiguity and nondeterminism in finite automata, Succinct representations of languages by DFA with different levels of reliability, Minimizing finite automata is computationally hard, From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity, Branching Measures and Nearly Acyclic NFAs, Measuring nondeterminism in pushdown automata, Pushdown automata with bounded nondeterminism and bounded ambiguity, Two-dimensional hierarchies of proper languages of lexicalized FRR-automata, Nondeterministic Tree Width of Regular Languages, Measuring nondeterminism in pushdown automata, State complexity of partial word finite automata, Communication complexity method for measuring nondeterminism in finite automata, Limitedness theorem on finite automata with distance functions: An algebraic proof, On reducing the number of stack symbols in a PDA, Worst Case Branching and Other Measures of Nondeterminism, Structural properties of NFAs and growth rates of nondeterminism measures
Cites Work
