Some remarks on synchronization, games and planar automata

dc.creatorMontoya, J. Andrés
dc.creatorNolasco, Christian
dc.date2017-09
dc.date2017
dc.date2018-02-26T16:08:30Z
dc.identifierhttp://sedici.unlp.edu.ar/handle/10915/65164
dc.descriptionAbstract—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.
dc.descriptionSociedad Argentina de Informática e Investigación Operativa (SADIO)
dc.formatapplication/pdf
dc.languageen
dc.rightshttp://creativecommons.org/licenses/by-sa/4.0/
dc.rightsCreative Commons Attribution-ShareAlike 4.0 International (CC BY-SA 4.0)
dc.subjectCiencias Informáticas
dc.subjectsynchronizing automaton
dc.subjectsynchronization games
dc.subjectĈerny conjectured
dc.titleSome remarks on synchronization, games and planar automata
dc.typeObjeto de conferencia
dc.typeObjeto de conferencia


Este ítem pertenece a la siguiente institución