On the Non-deterministic Communication Complexity of Regular Languages
From MaRDI portal
Publication:3533002
DOI10.1007/978-3-540-85780-8_7zbMATH Open1161.68597OpenAlexW1607180512MaRDI QIDQ3533002FDOQ3533002
Authors: Anil Ada 
Publication date: 30 October 2008
Published in: Developments in Language Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-85780-8_7
Recommendations
- On the non-deterministic communication complexity of regular languages
- Complete classifications for the communication complexity of regular languages
- scientific article; zbMATH DE number 1962802
- Communication complexity method for measuring nondeterminism in finite automata
- Nondeterministic Communication with a Limited Number of Advice Bits
Analysis of algorithms and problem complexity (68Q25) Algebraic theory of languages and automata (68Q70)
Cites Work
- Title not available (Why is that?)
- Expressing combinatorial optimization problems by linear programs
- Title not available (Why is that?)
- Communication Complexity
- On the power of small-depth threshold circuits
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- Title not available (Why is that?)
- Complete classifications for the communication complexity of regular languages
- Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
- Title not available (Why is that?)
- Polynomial closure and unambiguous product
- On the Non-deterministic Communication Complexity of Regular Languages
Cited In (12)
- Title not available (Why is that?)
- Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Survey on Fooling Sets as Effective Tools for Lower Bounds on Nondeterministic Complexity
- Information rate of some classes of non-regular languages: an automata-theoretic approach (extended abstract)
- Languages with Bounded Multiparty Communication Complexity
- On the non-deterministic communication complexity of regular languages
- Information rate of some classes of non-regular languages: an automata-theoretic approach
- On the Non-deterministic Communication Complexity of Regular Languages
- On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's
- Complete classifications for the communication complexity of regular languages
This page was built for publication: On the Non-deterministic Communication Complexity of Regular Languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3533002)
