Complete classifications for the communication complexity of regular languages

DOI10.1007/s00224-004-1190-2zbMath1066.68073OpenAlexW2071784365MaRDI QIDQ1771314

Pascal Tesson, Denis Thérien

Publication date: 19 April 2005

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-004-1190-2

zbMATH Keywords

two-party communication complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (8)

Complexity Analysis: Transformation Monoids of Finite Automata ⋮ The complexity of intersecting finite automata having few final states ⋮ Unnamed Item ⋮ On the Non-deterministic Communication Complexity of Regular Languages ⋮ Circuit complexity of regular languages ⋮ WEAKLY ITERATED BLOCK PRODUCTS AND APPLICATIONS TO LOGIC AND COMPLEXITY ⋮ ON THE NON-DETERMINISTIC COMMUNICATION COMPLEXITY OF REGULAR LANGUAGES ⋮ An Algebraic Perspective on Boolean Function Learning

This page was built for publication: Complete classifications for the communication complexity of regular languages