Some remarks on synchronization, games and planar automata

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...

Descripción completa

Detalles Bibliográficos
Autores principales: Montoya, J. Andrés, Nolasco, Christian
Formato: Objeto de conferencia
Lenguaje:Inglés
Publicado: 2017
Materias:
Ciencias Informáticas
synchronizing automaton
synchronization games
Ĉerny conjectured
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/65164
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-65164
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Informáticas
synchronizing automaton
synchronization games
Ĉerny conjectured
spellingShingle Ciencias Informáticas
synchronizing automaton
synchronization games
Ĉerny conjectured
Montoya, J. Andrés
Nolasco, Christian
Some remarks on synchronization, games and planar automata
topic_facet Ciencias Informáticas
synchronizing automaton
synchronization games
Ĉerny conjectured
description 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.
format Objeto de conferencia
Objeto de conferencia
author Montoya, J. Andrés
Nolasco, Christian
author_facet Montoya, J. Andrés
Nolasco, Christian
author_sort Montoya, J. Andrés
title Some remarks on synchronization, games and planar automata
title_short Some remarks on synchronization, games and planar automata
title_full Some remarks on synchronization, games and planar automata
title_fullStr Some remarks on synchronization, games and planar automata
title_full_unstemmed Some remarks on synchronization, games and planar automata
title_sort some remarks on synchronization, games and planar automata
publishDate 2017
url http://sedici.unlp.edu.ar/handle/10915/65164
work_keys_str_mv AT montoyajandres someremarksonsynchronizationgamesandplanarautomata
AT nolascochristian someremarksonsynchronizationgamesandplanarautomata
bdutipo_str Repositorios
_version_ 1764820480202637312

Ejemplares similares