We investigate two cooperative variants (with and without lies) of the Guessing Secrets problem, introduced in [L Chung, R. Graham, F.T. Leighton, Guessing secrets, Electronic journal of Combinatorics 8 (2001)] in the attempt to model an interactive situation arising in the World Wide Web, in relation to the efficient delivery of Internet content. After placing bounds on the cardinality of the smallest set of questions needed to win the game, we establish that the algebra of all the states of knowledge induced by any designated game is a pseudocomplemented lattice. In particular, its join semilattice reduct is embeddable into the corresponding reduct of the Boolean algebra 2(N-1), where N is the cardinality, of the search space. (C) 2009 Elsevier Inc. All rights reserved.

Sergioli, G., Ledda, A., Paoli, F., Giuntini, R., Kowalski, T., Montagna, F., et al. (2009). Two cooperative versions of the Guessing Secrets problem. INFORMATION SCIENCES, 179(20), 3645-3658 [10.1016/j.ins.2009.06.014].

Two cooperative versions of the Guessing Secrets problem

MONTAGNA, FRANCO;MARINI, CLAUDIO
2009-01-01

Abstract

We investigate two cooperative variants (with and without lies) of the Guessing Secrets problem, introduced in [L Chung, R. Graham, F.T. Leighton, Guessing secrets, Electronic journal of Combinatorics 8 (2001)] in the attempt to model an interactive situation arising in the World Wide Web, in relation to the efficient delivery of Internet content. After placing bounds on the cardinality of the smallest set of questions needed to win the game, we establish that the algebra of all the states of knowledge induced by any designated game is a pseudocomplemented lattice. In particular, its join semilattice reduct is embeddable into the corresponding reduct of the Boolean algebra 2(N-1), where N is the cardinality, of the search space. (C) 2009 Elsevier Inc. All rights reserved.
2009
Sergioli, G., Ledda, A., Paoli, F., Giuntini, R., Kowalski, T., Montagna, F., et al. (2009). Two cooperative versions of the Guessing Secrets problem. INFORMATION SCIENCES, 179(20), 3645-3658 [10.1016/j.ins.2009.06.014].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11365/7139
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo