On measuring nondeterminism in regular languages

DOI10.1016/0890-5401(90)90053-KMaRDI QIDQ912641zbMATH OpenFDO

Authors Jonathan Goldstine, Detlef Wotschke, Chandra M. R. Kintala

Publication date 1990

Published in Information and Computation (Search for Journal in Brave)

zbMATH Keywords

lower boundsnondeterminismupper boundscomputabilityfinite automatonspectrum of a regular language

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Recommendations

• On the relation between ambiguity and nondeterminism in finite automata
• scientific article; zbMATH DE number 1670824
• Measuring nondeterminism in pushdown automata
• Ambiguity, nondeterminism and state complexity of finite automata
• On the degree of ambiguity of finite automata

Cites work

• scientific article; zbMATH DE number 3839323 (Why is no real title available?)
• Amounts of nondeterminism in finite automata
• Limitedness theorem on finite automata with distance functions
• On the topological structure of a finitely generated semigroup of matrices
• Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations

Cited in

(35)

• Converting finite width AFAs to nondeterministic and universal finite automata
• Regular sensing
• Left is Better Than Right for Reducing Nondeterminism of NFAs
• Pushdown automata with bounded nondeterminism and bounded ambiguity
• 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
• Context-dependent nondeterminism for pushdown automata
• A Survey on Fooling Sets as Effective Tools for Lower Bounds on Nondeterministic Complexity
• A Measure for the Degree of Nondeterminism of Context-Free Languages
• Measuring nondeterminism in pushdown automata
• Minimizing finite automata is computationally hard
• Measures of nondeterminism for pushdown automata
• Succinct representations of languages by DFA with different levels of reliability
• Pushdown automata with bounded nondeterminism and bounded ambiguity
• Branching measures and nearly acyclic NFAs
• Worst Case Branching and Other Measures of Nondeterminism
• Regulated Nondeterminism in Pushdown Automata
• On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata
• Communication complexity method for measuring nondeterminism in finite automata
• Descriptional complexity of finite automata -- selected highlights
• On finite automata with limited nondeterminism (extended abstract)
• Measuring nondeterminism in pushdown automata
• Structural properties of NFAs and growth rates of nondeterminism measures
• Operational state complexity of unary NFAs with finite nondeterminism
• In memoriam Chandra Kintala
• On reducing the number of stack symbols in a PDA
• Nondeterministic tree width of regular languages
• Two-dimensional hierarchies of proper languages of lexicalized FRR-automata
• From finite automata to regular expressions and back -- a summary on descriptional complexity
• Existential and universal width of alternating finite automata
• On the relation between ambiguity and nondeterminism in finite automata
• Limitedness theorem on finite automata with distance functions: An algebraic proof
• Distance automata having large finite distance or finite ambiguity
• State complexity of partial word finite automata
• On Usefulness of Information: Framework and NFA Case

This page was built for publication: On measuring nondeterminism in regular languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q912641)