Recognizable Picture Languages: Separating UREC from coUREC via Communication Complexity
En palabras de los autores
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.
Resultado principalEl resumen no menciona limitaciones.
Apareció: miércoles, 23 de septiembre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 18 pages, 7 figures