Jazyky s omezenou komunikační složitostí pro více hráčů

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F07%3A00084614" target="_blank" >RIV/67985840:_____/07:00084614 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Languages with Bounded Multiparty Communication Complexity

Popis výsledku v původním jazyce

We study languages with bounded communication complexity in the multiparty "input on the forehead" model with worst-case partition. In the two party case,it is known that such languages are exactly those that are recognized by programs over commutative monoids.This can be used to show that these languages can be computed by shallow ACC^0 circuits. In contrast, we use coding techniques to show that there are languages of arbitrarily large circuit complexity than can be computed by k players using constant communication, if>=3. However, if the language has a neutral letter and constant communication complexity for k players for some fixed k, then the language is in fact regular. We give an algebraic characterization of regular languages with this property. We also prove than a symmetric language has bounded k-party communication complexity for some fixed k iff it has bounded 2-party communication complexity.

Název v anglickém jazyce

Languages with Bounded Multiparty Communication Complexity

Popis výsledku anglicky

We study languages with bounded communication complexity in the multiparty "input on the forehead" model with worst-case partition. In the two party case,it is known that such languages are exactly those that are recognized by programs over commutative monoids.This can be used to show that these languages can be computed by shallow ACC^0 circuits. In contrast, we use coding techniques to show that there are languages of arbitrarily large circuit complexity than can be computed by k players using constant communication, if>=3. However, if the language has a neutral letter and constant communication complexity for k players for some fixed k, then the language is in fact regular. We give an algebraic characterization of regular languages with this property. We also prove than a symmetric language has bounded k-party communication complexity for some fixed k iff it has bounded 2-party communication complexity.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/GA201%2F05%2F0124" target="_blank" >GA201/05/0124: Online algoritmy, náhodnost a extremální problémy</a><br>

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2007

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceeding of the 24th Annual Symposium on Theoretical Aspects of Computer Science (STACS), 2007

ISBN

978-3-540-70917-6

ISSN

—

e-ISSN

—

Počet stran výsledku

11

Strana od-do

500-511

Název nakladatele

Springer-Verlag

Místo vydání

Berlin

Místo konání akce

Aachen

Datum konání akce

22. 2. 2007

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—