Abstract—We study synchronization games on planar automata.
We prove that recognizing the planar games that can be won by the synchronizer is a co-NP hard problem. We prove some additional results indicating that planar games are as hard as nonplanar games. Those results amount to show that planar automata are representative of the intricacies of automata synchronization.
Información general
Fecha de exposición:septiembre 2017
Fecha de publicación:2017
Idioma del documento:Inglés
Evento:Simposio Latinoamericano de Teoría Computacional (SLTC) - JAIIO 46 (Córdoba, 2017).
Institución de origen:Sociedad Argentina de Informática e Investigación Operativa (SADIO)
Excepto donde se diga explícitamente, este item se publica bajo la siguiente licencia Creative Commons Attribution-ShareAlike 4.0 International (CC BY-SA 4.0)