Communication complexity method for measuring nondeterminism in finite automata
From MaRDI portal
Recommendations
Cites work
- A comparison of two lower-bound methods for communication complexity
- Communication Complexity
- scientific article; zbMATH DE number 1670824 (Why is no real title available?)
- scientific article; zbMATH DE number 3978429 (Why is no real title available?)
- scientific article; zbMATH DE number 4026854 (Why is no real title available?)
- scientific article; zbMATH DE number 3497806 (Why is no real title available?)
- scientific article; zbMATH DE number 1256774 (Why is no real title available?)
- scientific article; zbMATH DE number 1335889 (Why is no real title available?)
- scientific article; zbMATH DE number 1011685 (Why is no real title available?)
- scientific article; zbMATH DE number 1857650 (Why is no real title available?)
- scientific article; zbMATH DE number 1405658 (Why is no real title available?)
- scientific article; zbMATH DE number 4197419 (Why is no real title available?)
- scientific article; zbMATH DE number 3254905 (Why is no real title available?)
- Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations
- Lower bounds on the size of sweeping automata
- Non-deterministic communication complexity with few witnesses
- On measuring nondeterminism in regular languages
- On rank vs. communication complexity
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
- On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
- On the power of Las Vegas II: Two-way finite automata
- On the relation between ambiguity and nondeterminism in finite automata
- Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
- Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
- Translating regular expressions into small -free nondeterministic finite automata
- Two-way deterministic finite automata are exponentially more succinct than sweeping automata
Cited in
(50)- State complexity of unique rational operations
- State complexity of some operations on binary regular languages
- Two-dimensional models
- Width measures of alternating finite automata
- Deciding path size of nondeterministic (and input-driven) pushdown automata
- Structural properties of NFAs and growth rates of nondeterminism measures
- Nondeterministic syntactic complexity
- 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
- Communication complexity tools on recognizable picture languages
- On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-k-times branching programs
- scientific article; zbMATH DE number 1670824 (Why is no real title available?)
- From finite automata to regular expressions and back -- a summary on descriptional complexity
- Operations on Unambiguous Finite Automata
- In memoriam Chandra Kintala
- Classes of two-dimensional languages and recognizability conditions
- Comparing necessary conditions for recognizability of two-dimensional languages
- Deterministic blow-ups of minimal NFA's
- Unambiguous recognizable two-dimensional languages
- 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
- On the Non-deterministic Communication Complexity of Regular Languages
- DETERMINISTIC BLOW-UPS OF MINIMAL NONDETERMINISTIC FINITE AUTOMATA OVER A FIXED ALPHABET
- On the non-deterministic communication complexity of regular languages
- Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
- Unambiguous finite automata over a unary alphabet
- scientific article; zbMATH DE number 2050931 (Why is no real title available?)
- scientific article; zbMATH DE number 2068869 (Why is no real title available?)
- Operations on Unambiguous Finite Automata
- Descriptional complexity of unambiguous input-driven pushdown automata
- Branching measures and nearly acyclic NFAs
- Worst Case Branching and Other Measures of Nondeterminism
- Ambiguity, nondeterminism and state complexity of finite automata
- Ambiguity and communication
- Ambiguity and communication
- STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
- Nondeterministic tree width of regular languages
- DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
- Left is Better Than Right for Reducing Nondeterminism of NFAs
- Converting finite width AFAs to nondeterministic and universal finite automata
- On Usefulness of Information: Framework and NFA Case
- Probabilism versus Alternation for Automata
- Existential and universal width of alternating finite automata
- Descriptional complexity of finite automata -- selected highlights
- Improved upper bounds for determinizing NIDPDAs with limited nondeterminism
- Existential and universal width of alternating finite automata
- Maximal universal width of an AFA is NP-hard
- Decidability, undecidability, and PSPACE-completeness of the twins property in the tropical semiring
- Context-dependent nondeterminism for pushdown automata
- Operational state complexity of unary NFAs with finite nondeterminism
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)
