Probabilistic variants of Renyi-Ulam game and many-valued logic

• Autorzy: Marini C. , Montagna F.
• Języki publikacji: EN

Abstrakty

EN

In this paper we discuss some generalizations of Renyi-Ulam game with lies: some of them are simply probabilistic variants of it, some others differ from it by the presence of more than one number to guess. In the last part of the paper, we also discuss the relationship between such variants and many-valued logic. This paper is just a survey of known results, but in its last part it also contains some plans for future research.

Słowa kluczowe

EN

Renyi-Ulam game; guessing secrets

• Wydawca: Politechnika Gdańska
• Czasopismo: TASK Quarterly : scientific bulletin of Academic Computer Centre in Gdansk
• Rocznik: 2005
• Tom: Vol. 9, No 3
• Strony: 317--335
• Opis fizyczny: Bibliogr. 23 poz.

Twórcy

autor

Marini C.

• Dipartimento di Scienze Matematiche ed Informatiche, Universit`a degli Studi di Siena, Pian dei Mantellini 44, 53100 Siena, Italy

autor

Montagna F.

• Dipartimento di Scienze Matematiche ed Informatiche, Universit`a degli Studi di Siena, Pian dei Mantellini 44, 53100 Siena, Italy

Bibliografia

• [1] R´enyi A 1976 Napl´o az inform´aci´oelm´eletr˝ol, Gondolat, Budapest; English translation: 1984 A Diary on Information Theory, J. Wiley and Sons, New York
• [2] Rivest R L, Meyer A R, Kleitman D J, Winklmann K and Spencer J 1980 J. Comput. System Sci. 20 396
• [3] Deppe C 2004 Coding with Feedback and Searching with Lies, Bolyai Soc. Studies, Springer
• [4] Pelc A 2002 Theoretical Computer Science 270 71
• [5] Pelc A 1989 Theoretical Computer Science 63 185
• [6] Cicalese F, Mundici D and Vaccaro U 2002 Rota-Metropolis Cubic Logic and Ulam-Renyi Games, in: Algebraic Combinatorics and Computer Science: in Memoriam Gian-Carlo Rota, Springer, pp. 197–244
• [7] Hill R 1995 Searching with Lies, Surveys in Combinatorics, Cambridge University Press, pp. 41–70
• [8] Peterson W W and Weldon E J Jr 1972 Error-Correcting Codes, 2nd Edition, MIT Press, Cambridge, Mass
• [9] Cicalese F and Mundici D 2000 Optimal Coding with One Asymmetric Error: Below the Sphere Packing Bound, COCOON, pp. 159–169
• [10] Cicalese F, Mundici D and Vaccaro U 2002 Theoretical Computer Science 270 (1-2) 877
• [11] Du D Z and Hwang F K 2000 Combinatorial Group Testing and Its Applications, World Scientific Pub Co.
• [12] Chung F, Graham R and Leighton T 2001 The Electronic Journal of Combinatorics 8 ]R13
• [13] Mundici D 1991 Proc. Int. Congress of the Italian Society for Logic and Philosophy of Science, SILFS, vol. 2, CLUEB, Bologna, pp. 151–162
• [14] Mundici D, Cignoli R and Ottaviano I M L D 2000 Algebraic Foundations of Many-valued Reasoning, Trends in Logic Series Studia Logica Library 7, Kluwer, Dordrecht
• [15] Berlekamp E R 1968 Block Coding for the Binary Symmetric Channel with Noiseless, Delayless Feedback, in: Error-Correcting Codes, Wiley, New York, pp. 61–85
• [16] Spencer J and Winkler P 1992 Combinatorics, Probability and Computing 1 81
• [17] Durrett R 1991 Probability: Theory and Examples, Belmont, CA, Wadsworth
• [18] Del Lungo A, Louchard G, Marini C and Montagna F 2005 J. Algorithms 55 142
• [19] H´ajek P 1998 Metamathematics of Fuzzy Logic, Kluwer
• [20] Dummett M 1959 J. Symbo. Log. 24 96
• [21] Flaminio T and Montagna F 2004 Proc. of the 10 th Int. Conf. IPMU, Perugia, Italy, pp. 493–499
• [22] Esteva F, Godo L and H´ajek P, 2000 Neural Network World 5/00 811
• [23] Montagna F 2000 J. of Logic, Language and Information 9 91