=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."> =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."> Languages with Bounded Multiparty Communication Complexity
Počet záznamů: 1  

Languages with Bounded Multiparty Communication Complexity

    1.
    SYSNO ASEP0084614
    Druh ASEPC - Konferenční příspěvek (mezinárodní konf.)
    Zařazení RIVD - Článek ve sborníku
    NázevLanguages with Bounded Multiparty Communication Complexity
    Překlad názvuJazyky s omezenou komunikační složitostí pro více hráčů
    Tvůrce(i) Chattopadhyay, A. (CA)
    Koucký, Michal (MU-W) RID, SAI, ORCID
    Krebs, A. (DE)
    Szegedy, M. (US)
    Tesson, P. (CA)
    Thérien, D. (CA)
    Zdroj.dok.Proceeding of the 24th Annual Symposium on Theoretical Aspects of Computer Science (STACS), 2007. - Berlin : Springer-Verlag, 2007 / Thomas W. ; Weil P. - ISBN 978-3-540-70917-6
    Rozsah strans. 500-511
    Poč.str.11 s.
    AkceAnnual Symposium on Theoretical Aspects of Computer Science (STACS)
    Datum konání22.02.2007-24.02.2007
    Místo konáníAachen
    ZeměDE - Německo
    Typ akceWRD
    Jazyk dok.eng - angličtina
    Země vyd.DE - Německo
    Klíč. slovacommunication complexity ; codes ; Ramsey theory
    Vědní obor RIVBA - Obecná matematika
    CEPGA201/05/0124 GA ČR - Grantová agentura ČR
    CEZAV0Z10190503 - MU-W (2005-2011)
    AnotaceWe 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.
    PracovištěMatematický ústav
    KontaktJarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757
    Rok sběru2008
Počet záznamů: 1  

  Tyto stránky využívají soubory cookies, které usnadňují jejich prohlížení. Další informace o tom jak používáme cookies.

Přijmout všeNastaveníOdmítnout vše