ON THE NON-DETERMINISTIC COMMUNICATION COMPLEXITY OF REGULAR LANGUAGES

DOI10.1142/S0129054110007386zbMath1205.68188MaRDI QIDQ3586400

Anil Ada

Publication date: 6 September 2010

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

zbMATH Keywords

regular languagescommunication complexityalgebraic automata theory

Mathematics Subject Classification ID

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

Cites Work

• On the power of small-depth threshold circuits
• Expressing combinatorial optimization problems by linear programs
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• Polynomial closure and unambiguous product
• Complete classifications for the communication complexity of regular languages
• Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity

This page was built for publication: ON THE NON-DETERMINISTIC COMMUNICATION COMPLEXITY OF REGULAR LANGUAGES