On lattices from combinatorial game theory modularity and a representation theorem: finite case


Autoria(s): Carvalho, Alda Cristina Jesus V. Nunes de; Santos, Carlos Pereira dos; Dias, Cátia Sofia Peniche Lente Dinis; Coelho, Francisco; Neto, João Pedro; Nowakowski, Richard; Vinagre, Sandra
Data(s)

25/08/2015

25/08/2015

01/03/2014

Resumo

We show that a self-generated set of combinatorial games, S. may not be hereditarily closed but, strong self-generation and hereditary closure are equivalent in the universe of short games. In [13], the question "Is there a set which will give a non-distributive but modular lattice?" appears. A useful necessary condition for the existence of a finite non-distributive modular L(S) is proved. We show the existence of S such that L(S) is modular and not distributive, exhibiting the first known example. More, we prove a Representation Theorem with Games that allows the generation of all finite lattices in game context. Finally, a computational tool for drawing lattices of games is presented. (C) 2014 Elsevier B.V. All rights reserved.

Identificador

CARVALHO, Alda Cristina Jesus V. Nunes de, [et al] – On lattices from combinatorial game theory modularity and a representation theorem: Finite case. Theroretical Computer Science. ISSN: 0304-3975. Vol. 527 (2014), pp. 37-49

0304-3975

1879-2294

http://hdl.handle.net/10400.21/5012

10.1016/j.tcs.2014.01.025

Idioma(s)

eng

Publicador

Elsevier Science BV

Direitos

closedAccess

Palavras-Chave #Combinatorial game theory #Lattices #Modularity #Representation theorems
Tipo

article