Recognizable Picture Languages: Separating UREC from coUREC via Communication Complexity
In the authors' words
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\"o\"os et al. (2022), although its implementation in the setting of picture languages requires substantially different technical ingredients.
Main resultThe abstract does not state a limitation.
Appeared: Wednesday, September 23. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 18 pages, 7 figures