On the Non-deterministic Communication Complexity of Regular Languages

DOI10.1007/978-3-540-85780-8_7MaRDI QIDQ3533002zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algebraic theory of languages and automata (68Q70)

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

Cites work

• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 1223708 (Why is no real title available?)
• scientific article; zbMATH DE number 1256663 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• Communication Complexity
• Complete classifications for the communication complexity of regular languages
• Expressing combinatorial optimization problems by linear programs
• Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• On the Non-deterministic Communication Complexity of Regular Languages
• On the power of small-depth threshold circuits
• Polynomial closure and unambiguous product

Cited in

(12)

• On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's
• On the Non-deterministic Communication Complexity of Regular Languages
• Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
• Languages with Bounded Multiparty Communication Complexity
• scientific article; zbMATH DE number 2050931 (Why is no real title available?)
• A Survey on Fooling Sets as Effective Tools for Lower Bounds on Nondeterministic Complexity
• On the non-deterministic communication complexity of regular languages
• Information rate of some classes of non-regular languages: an automata-theoretic approach (extended abstract)
• scientific article; zbMATH DE number 1962802 (Why is no real title available?)
• Complete classifications for the communication complexity of regular languages
• scientific article; zbMATH DE number 1948494 (Why is no real title available?)
• Information rate of some classes of non-regular languages: an automata-theoretic approach

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)