Browsing by Author "Liprandi, Maximiliano"
Now showing 1 - 2 of 2
Results Per Page
Sort Options
Item Open Access Bounded Width Dichotomies in Constraint Satisfaction Problems(2018-06-07) Liprandi, Maximiliano; Laflamme, Claude; Woodrow, Robert E.; Cavers, Michael S.; Cockett, J. Robin B.; Bonato, AnthonyIn this thesis we examine the connection between structures with bounded width, polymorphisms and pebble games. There has been extensive work on trying to prove the dichotomy conjecture for finite structures, namely, the Constraint Satisfaction Problem (CSP) of a finite structure is either in P or NP-complete. We are interested in finding classes in which a stronger dichotomy exists; namely, where every structure has either bounded width or a hard CSP. We call this kind of dichotomy a bounded width dichotomy. We will investigate properties of polymorphisms of structures with bounded width, and use this to look at classes of directed graphs with a bounded width dichotomy.Item Open Access Can some simple games lead to chaos?(2013-01-07) Liprandi, Maximiliano; Guy, RichardSome combinatorial games, like GRUNDY'S GAME, are simple to describe, but follow chaotic patterns and can prove very difficult to analyze entirely. In this thesis we will look at some games, including a combinatorial version of Mancala; the game of BLASH & SLASH, played by drawing diagonals on a rectangular grid; and BLASH, SLASH & DASH, played by removing edges in triangular arrays. While some of these games might seem very simple at a first, they often exhibit patterns that are very hard to predict. In Chapters 1 and 2 we give an introduction to the subject of combinatorial games by looking at the theories crafted by Conway and by Sprague and Grundy before him. In Chapter 3 we analyze the game of BLASH & SLASH in some of its versions, and find an equivalence between this game and NODE KAYLES. In Chapter 4 we look at the game of BLASH, SLASH & DASH and find a sparse space in one of its cases. In Chapter 5 we analyze some versions of BASIC MANCALA. Lastly, we give suggestions for future research in these games.