Upload resources

Upload your works to SEDICI to increase its visibility and improve its impact

 

Some remarks on synchronization, games and planar automata

Document type: Objeto de conferencia

Abstract

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.

General information

Exposure date: septiembre 2017
Issue date: 2017
Document language: English
Event: Simposio Latinoamericano de Teoría Computacional (SLTC) - JAIIO 46 (Córdoba, 2017).
Origin: Sociedad Argentina de Informática e Investigación Operativa (SADIO)
xmlui.dri2xhtml.METS-1.0.item-dc-subject: synchronizing automaton ; synchronization games ; Ĉerny conjectured
Subjects: Ciencias Informáticas

Download Files

Thumbnail
Documento completo
Download file (256.2Kb) - PDF
 
Created: 26 de febrero de 2018
Available since: 26 de febrero de 2018
Please, use one of this identificators(URI) for cite o linking this item:
  • http://sedici.unlp.edu.ar/handle/10915/65164

    • This item appears in the following Collection(s)

    Creative Commons Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) Except where otherwise noted, this item's license is described as Creative Commons Attribution-ShareAlike 4.0 International (CC BY-SA 4.0)