Papers for

language and automata theorists

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Communication complexity shows limits in recognizable picture languages

Recognizable Picture Languages: Separating UREC from coUREC via Communication Complexity

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.

Tue 22 SeptFormal Languages and Automata TheoryComputational Complexity
The gist
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.
Open → 2609.26047v1