Communication complexity shows limits in recognizable picture languages
Recognizable Picture Languages: Separating UREC from coUREC via Communication Complexity
Formal Languages and Automata TheoryComputational Complexity
Summary
This paper deals with a special kind of languages made up of pictures instead of words, called recognizable picture languages. The authors solved a long-standing question by showing that some languages in this group behave very differently from their opposites. To do this, the authors used ideas from communication complexity, which studies how hard it is for two parties to share information efficiently. Their work builds on recent advances but needed new techniques because pictures are more complicated than words.
What this means in practice
- •For language and automata theorists: Clarifies which recognizable picture languages have complements that are also recognizable, influencing the design of language-processing algorithms.
- •For complexity theorists: Provides new methods to prove limits on computational models that handle two-dimensional data, guiding development of verification tools.
A theory result. No direct application yet.
Authors
Antonin Callard, Andrei Romashchenko, Véronique Terrier, Pascal Vanier
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.