Communication complexity method for measuring nondeterminism in finite automata

DOI10.1006/inco.2001.3069zbMath1009.68067OpenAlexW2057747677WikidataQ58040242 ScholiaQ58040242MaRDI QIDQ1854501

Georg Schnitger, Hartmut Klauck, Sebastian Seibert, Juraj Hromkovič, Juhani Karhumäki

Publication date: 14 January 2003

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

Full work available at URL: https://doi.org/10.1006/inco.2001.3069

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-\(k\)-times branching programs ⋮ IN MEMORIAM CHANDRA KINTALA ⋮ Context-dependent nondeterminism for pushdown automata ⋮ 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 ⋮ Probabilism versus Alternation for Automata ⋮ Existential and universal width of alternating finite automata ⋮ A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata ⋮ On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes ⋮ DETERMINISTIC BLOW-UPS OF MINIMAL NONDETERMINISTIC FINITE AUTOMATA OVER A FIXED ALPHABET ⋮ Operations on Unambiguous Finite Automata ⋮ Descriptional complexity of unambiguous input-driven pushdown automata ⋮ Classes of two-dimensional languages and recognizability conditions ⋮ DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY ⋮ Nondeterministic syntactic complexity ⋮ Comparing Necessary Conditions for Recognizability of Two-Dimensional Languages ⋮ Ambiguity and communication ⋮ State complexity of some operations on binary regular languages ⋮ Nondeterministic state complexity of nested word automata ⋮ On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's ⋮ Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity ⋮ From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity ⋮ Branching Measures and Nearly Acyclic NFAs ⋮ STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION ⋮ Operations on Unambiguous Finite Automata ⋮ State complexity of unique rational operations ⋮ Decidability, undecidability, and PSPACE-completeness of the twins property in the tropical semiring ⋮ Two-dimensional models ⋮ Nondeterministic Tree Width of Regular Languages ⋮ Communication complexity tools on recognizable picture languages ⋮ Deterministic blow-ups of minimal NFA's ⋮ Width measures of alternating finite automata ⋮ Unambiguous recognizable two-dimensional languages ⋮ Deciding path size of nondeterministic (and input-driven) pushdown automata ⋮ Worst Case Branching and Other Measures of Nondeterminism ⋮ Structural properties of NFAs and growth rates of nondeterminism measures

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On measuring nondeterminism in regular languages
• Lower bounds on the size of sweeping automata
• Two-way deterministic finite automata are exponentially more succinct than sweeping automata
• On the relation between ambiguity and nondeterminism in finite automata
• Non-deterministic communication complexity with few witnesses
• A comparison of two lower-bound methods for communication complexity
• On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
• On rank vs. communication complexity
• 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
• Communication Complexity
• Translating regular expressions into small ε-free nondeterministic finite automata
• Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
• On the power of Las Vegas II: Two-way finite automata