SW-type puzzles and their graphs

Nagy Benedek: SW-type puzzles and their graphs. In: Acta cybernetica, (16) 1. pp. 67-82. (2003)

[thumbnail of cybernetica_016_numb_001_067-082.pdf]
Cikk, tanulmány, mű

Download (1MB) | Preview


In this paper, we present the SW-type of truth-tellers and liars puzzles. We examine the SW-type puzzles where each person can utter a sentence about the person's type and in which he uses only the "and" connective. We make the graphs of these puzzles. The graph of a puzzle has all information about the puzzle if we have no other information to solve the puzzle than the statements given (clear puzzles). We analyze the graphs of the possible puzzles. We give some transformations of graphs based on local information, for instance arrow-adding steps. These local steps are very helpful to solve these puzzles. We show an example that we can solve using these local steps. After this, we examine into the global properties of the graphs. We show a special example when the local steps do not help, but the puzzle is solvable by using global information. Finally we show a graph-algorithm which is a combination of local and global information, and show that it can solve the SW-type puzzles.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 2003
Volume: 16
Number: 1
ISSN: 0324-721X
Page Range: pp. 67-82
Language: English
Place of Publication: Szeged
Event Title: Conference for PhD Students in Computer Science (3.) (2002) (Szeged)
Related URLs: http://acta.bibl.u-szeged.hu/38515/
Uncontrolled Keywords: Számítástechnika, Kibernetika
Additional Information: Bibliogr.: 82. p. ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2016. Oct. 15. 12:25
Last Modified: 2022. Jun. 15. 08:16
URI: http://acta.bibl.u-szeged.hu/id/eprint/12710

Actions (login required)

View Item View Item