Carregant...
Carregant...

Vés al contingut (premeu Retorn)

On the hardness of game equivalence under local isomorphism

Autor
Gabarro, J.; Garcia, A.; Serna, M.
Tipus d'activitat
Article en revista
Revista
RAIRO. Theoretical informatics and applications
Data de publicació
2013-04
Volum
47
Número
2
Pàgina inicial
147
Pàgina final
169
DOI
https://doi.org/10.1051/ita/2012024 Obrir en finestra nova
Resum
We introduce a type of isomorphism among strategic games that we call local isomorphism. Local isomorphisms is a weaker version of the notions of strong and weak game isomorphism introduced in [J. Gabarro, A. Garcia and M. Serna, Theor. Comput. Sci. 412 (2011) 6675-6695]. In a local isomorphism it is required to preserve, for any player, the player's preferences on the sets of strategy profiles that differ only in the action selected by this player. We show that the game isomorphism problem for ...
Paraules clau
Boolean formula isomorphism, Circuit isomorphism, Computational complexity, Formula games, Game isomorphism, Graph isomorphism, Strategic games, Succinct representations
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants