Communication complexity method for measuring nondeterminism in finite automata
From MaRDI portal
Publication:1854501
DOI10.1006/INCO.2001.3069zbMATH Open1009.68067DBLPjournals/iandc/HromkovicSKKS02OpenAlexW2057747677WikidataQ58040242 ScholiaQ58040242MaRDI QIDQ1854501FDOQ1854501
Authors: Sebastian Seibert, Hartmut Klauck, Georg Schnitger, 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
Recommendations
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)
Cites Work
- Title not available (Why is that?)
- Communication Complexity
- On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
- Title not available (Why is that?)
- Non-deterministic communication complexity with few witnesses
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- Lower bounds on the size of sweeping automata
- Two-way deterministic finite automata are exponentially more succinct than sweeping automata
- On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
- On rank vs. communication complexity
- Title not available (Why is that?)
- Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
- Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
- Title not available (Why is that?)
- Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations
- On the power of Las Vegas II: Two-way finite automata
- Title not available (Why is that?)
- On the relation between ambiguity and nondeterminism in finite automata
- A comparison of two lower-bound methods for communication complexity
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- On measuring nondeterminism in regular languages
- Translating regular expressions into small \(\epsilon \)-free nondeterministic finite automata
- Title not available (Why is that?)
Cited In (47)
- Communication complexity tools on recognizable picture languages
- STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
- Deciding path size of nondeterministic (and input-driven) pushdown automata
- DETERMINISTIC BLOW-UPS OF MINIMAL NONDETERMINISTIC FINITE AUTOMATA OVER A FIXED ALPHABET
- Left is Better Than Right for Reducing Nondeterminism of NFAs
- Ambiguity and communication
- Ambiguity and communication
- Nondeterministic state complexity of nested word automata
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata
- Context-dependent nondeterminism for pushdown automata
- Operations on Unambiguous Finite Automata
- Unambiguous finite automata over a unary alphabet
- Probabilism versus Alternation for Automata
- DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
- Nondeterministic syntactic complexity
- State complexity of some operations on binary regular languages
- On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-\(k\)-times branching programs
- Branching measures and nearly acyclic NFAs
- Worst Case Branching and Other Measures of Nondeterminism
- Descriptional complexity of unambiguous input-driven pushdown automata
- Operations on Unambiguous Finite Automata
- Descriptional complexity of finite automata -- selected highlights
- On the non-deterministic communication complexity of regular languages
- State complexity of unique rational operations
- On the Non-deterministic Communication Complexity of Regular Languages
- Structural properties of NFAs and growth rates of nondeterminism measures
- Unambiguous recognizable two-dimensional languages
- In memoriam Chandra Kintala
- Operational state complexity of unary NFAs with finite nondeterminism
- Ambiguity, nondeterminism and state complexity of finite automata
- On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's
- Decidability, undecidability, and PSPACE-completeness of the twins property in the tropical semiring
- Nondeterministic tree width of regular languages
- Classes of two-dimensional languages and recognizability conditions
- Comparing necessary conditions for recognizability of two-dimensional languages
- From finite automata to regular expressions and back -- a summary on descriptional complexity
- Existential and universal width of alternating finite automata
- Two-dimensional models
- Deterministic blow-ups of minimal NFA's
- On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
- Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
- On Usefulness of Information: Framework and NFA Case
- Width measures of alternating finite automata
- Converting finite width AFAs to nondeterministic and universal finite automata
This page was built for publication: Communication complexity method for measuring nondeterminism in finite automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1854501)
