Skip to content
DraconiticResearch
Search Sources API
182,549 studies31 sourcesUpdated 24 min ago
PreprintCC BY 4.0HAL

Recognizable Picture Languages: Separating UREC from coUREC via Communication Complexity

  • Antonin Callard
  • Andrei Romashchenko
  • Véronique Terrier
  • Pascal Vanier
Open at sourcePDFCite

Abstract

We introduce communication-complexity lifting techniques into the study of recognizable picture languages. As an application, we resolve a long-standing open problem of Anselmo et al. ( 2006) by constructing a language in UREC whose complement does not belong to REC. Our lower-bound argument is inspired by the communication-complexity approach to unambiguous automata of Göös et al. (2022), although its implementation in the setting of picture languages requires substantially different technical ingredients.

Related

  1. A note on the nondeterministic communication complexity of equality
    Mathieu Hoyrup
    HALPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsHAL
  2. Infinite Communication Complexity and KW Games
    Evan Leach
    arXivPreprintarXiv licenceFull textLogic & foundationsarXiv
  3. Minimizing the Arithmetic and Communication Complexity of Jacobi's Method for Eigenvalues and Singular Values: Part Two -- Parallel Algorithms
    James Demmel, Hengrui Luo, Ryan Schneider +1
    arXivPreprintCC BY-NC-ND 4.0Full textNumerical analysis & scientific computingarXiv
  4. Array Rotation in Near-Field ISAC: Communication, Detection, and Estimation Under Low-Complexity Transmit Architectures
    Marziyeh Soltani, Mark F. Flanagan
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  5. Communication Complexity of Universal Features
    Lunjia Hu, Anish Jayant, Peter Li +2
    arXivPreprintarXiv licenceFull textStatisticsarXiv

Cite

BibTeXRIS
BibTeX
@misc{callard2026recognizable,
  title = {{Recognizable Picture Languages: Separating UREC from coUREC via Communication Complexity}},
  author = {Antonin Callard and Andrei Romashchenko and Véronique Terrier and Pascal Vanier},
  howpublished = {HAL},
  year = {2026},
  month = oct,
  url = {https://hal-lirmm.ccsd.cnrs.fr/lirmm-05758681v2},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Recognizable Picture Languages: Separating UREC from coUREC via Communication Complexity
AU  - Antonin Callard
AU  - Andrei Romashchenko
AU  - Véronique Terrier
AU  - Pascal Vanier
PY  - 2026
DA  - 2026/10/12
PB  - HAL
UR  - https://hal-lirmm.ccsd.cnrs.fr/lirmm-05758681v2
AB  - We introduce communication-complexity lifting techniques into the study of recognizable picture languages. As an application, we resolve a long-standing open problem of Anselmo et al. ( 2006) by constructing a language in UREC whose complement does not belong to REC. Our lower-bound argument is inspired by the communication-complexity approach to unambiguous automata of Göös et al. (2022), although its implementation in the setting of picture languages requires substantially different technical ingredients.
ER  -