Preprint
Sep 2026
Recognizable Picture Languages: Separating UREC from coUREC via Communication Complexity
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 communica...
Antonin Callard, Andrei E. Romashchenko, V. Terrier et al.
· 0 citations