On the non-deterministic communication complexity of regular languages

DOI10.1142/S0129054110007386MaRDI QIDQ3586400zbMATH OpenFDO

Authors Anil Ada

Publication date 6 September 2010

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054110007386

zbMATH Keywords

algebraic automata theorycommunication complexityregular languages

Mathematics Subject Classification ID

Semisimple Lie groups and their representations (22E46) Differential geometry of symmetric spaces (53C35) Noncompact Lie groups of transformations (57S20) Formal languages and automata (68Q45)

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

• 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 power of small-depth threshold circuits
• Polynomial closure and unambiguous product

Cited in

(8)

• Complete classifications for the communication complexity of regular languages
• On the Non-deterministic Communication Complexity of Regular Languages
• scientific article; zbMATH DE number 1948494 (Why is no real title available?)
• scientific article; zbMATH DE number 1962802 (Why is no real title available?)
• scientific article; zbMATH DE number 2050931 (Why is no real title available?)
• scientific article; zbMATH DE number 2068869 (Why is no real title available?)
• Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
• A Survey on Fooling Sets as Effective Tools for Lower Bounds on Nondeterministic Complexity

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 Q3586400)