Pavol Hell and Jaroslav Nesetril
- Published in print:
- 2004
- Published Online:
- September 2007
- ISBN:
- 9780198528173
- eISBN:
- 9780191713644
- Item type:
- book
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198528173.001.0001
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics
Graph theory is now an established discipline but the study of graph homomorphisms has only recently begun to gain wide acceptance and interest. This text is devoted entirely to the subject, bringing ...
More
Graph theory is now an established discipline but the study of graph homomorphisms has only recently begun to gain wide acceptance and interest. This text is devoted entirely to the subject, bringing together the highlights of the theory and its many applications. It looks at areas such as graph reconstruction, products, fractional and circular colourings, and constraint satisfaction problems, and has applications in complexity theory, artificial intelligence, telecommunications, and statistical physics. It has a wide focus on algebraic, combinatorial, and algorithmic aspects of graph homomorphisms. A reference list and historical summaries extend the material explicitly discussed. The book contains exercises of varying difficulty. Hints or references are provided for the more difficult exercises.Less
Graph theory is now an established discipline but the study of graph homomorphisms has only recently begun to gain wide acceptance and interest. This text is devoted entirely to the subject, bringing together the highlights of the theory and its many applications. It looks at areas such as graph reconstruction, products, fractional and circular colourings, and constraint satisfaction problems, and has applications in complexity theory, artificial intelligence, telecommunications, and statistical physics. It has a wide focus on algebraic, combinatorial, and algorithmic aspects of graph homomorphisms. A reference list and historical summaries extend the material explicitly discussed. The book contains exercises of varying difficulty. Hints or references are provided for the more difficult exercises.
Jennifer K. Robbennolt, Robert J. MacCoun, and John M. Darley
- Published in print:
- 2010
- Published Online:
- May 2010
- ISBN:
- 9780195367584
- eISBN:
- 9780199776917
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780195367584.003.0002
- Subject:
- Psychology, Forensic Psychology
Different models of judicial decision making highlight particular goals. Traditional legal theory posits that in making decisions judges strive to reach the correct legal decision as dictated by ...
More
Different models of judicial decision making highlight particular goals. Traditional legal theory posits that in making decisions judges strive to reach the correct legal decision as dictated by precedent. Attitudinal and strategic models focuses on the ways in which judges further their preferred policies. The managerial model emphasizes the increasing caseload pressures that judges at all levels face. Each model accurately captures some of what every judge does some of the time, but a sophisticated understanding of judicial decision making should explicitly incorporate the notion that judges simultaneously attempt to further numerous, disparate, and often conflicting, objectives. This chapter offers a preliminary account of a more psychologically plausible account of judicial cognition and motivation, based on principles of goal management in a constraint satisfaction network.Less
Different models of judicial decision making highlight particular goals. Traditional legal theory posits that in making decisions judges strive to reach the correct legal decision as dictated by precedent. Attitudinal and strategic models focuses on the ways in which judges further their preferred policies. The managerial model emphasizes the increasing caseload pressures that judges at all levels face. Each model accurately captures some of what every judge does some of the time, but a sophisticated understanding of judicial decision making should explicitly incorporate the notion that judges simultaneously attempt to further numerous, disparate, and often conflicting, objectives. This chapter offers a preliminary account of a more psychologically plausible account of judicial cognition and motivation, based on principles of goal management in a constraint satisfaction network.
Pavol Hell and Jaroslav Nešetřil
- Published in print:
- 2004
- Published Online:
- September 2007
- ISBN:
- 9780198528173
- eISBN:
- 9780191713644
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198528173.003.0005
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics
This chapter explores the algorithmic aspects of graph homomorphisms and of similar partition problems. The highlights include the dichotomy classification of graph homomorphisms to a fixed target ...
More
This chapter explores the algorithmic aspects of graph homomorphisms and of similar partition problems. The highlights include the dichotomy classification of graph homomorphisms to a fixed target graph $H$; a proof of the fact that dichotomy for digraph homomorphisms would imply dichotomy for all constraint satisfaction problems; a presentation of consistency-based algorithms; and associated dualities that seem to be applicable to all known polynomial cases of the digraph homomorphism problem. The role of polymorphisms in the design of polynomial algorithms is highlighted, and it is shown that graphs with the same set of polymorphisms define polynomially equivalent problems. The polymorphism known as the majority function is shown to yield a polynomial time homomorphism testing algorithm. The dichotomy classification of list homomorphism problems for reflexive graphs is presented. List matrix partition problems are posed in the language of trigraph homomorphisms, and the richness of the associated algorithms is illustrated on the case of clique cutsets and generalized split graphs.Less
This chapter explores the algorithmic aspects of graph homomorphisms and of similar partition problems. The highlights include the dichotomy classification of graph homomorphisms to a fixed target graph $H$; a proof of the fact that dichotomy for digraph homomorphisms would imply dichotomy for all constraint satisfaction problems; a presentation of consistency-based algorithms; and associated dualities that seem to be applicable to all known polynomial cases of the digraph homomorphism problem. The role of polymorphisms in the design of polynomial algorithms is highlighted, and it is shown that graphs with the same set of polymorphisms define polynomially equivalent problems. The polymorphism known as the majority function is shown to yield a polynomial time homomorphism testing algorithm. The dichotomy classification of list homomorphism problems for reflexive graphs is presented. List matrix partition problems are posed in the language of trigraph homomorphisms, and the richness of the associated algorithms is illustrated on the case of clique cutsets and generalized split graphs.
Paul Thagard, Chris Eliasmith, Paul Rusnock, and Cameron Shelley
- Published in print:
- 2002
- Published Online:
- February 2006
- ISBN:
- 9780195147667
- eISBN:
- 9780199785865
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/0195147669.003.0006
- Subject:
- Philosophy, Metaphysics/Epistemology
This chapter shows how epistemic coherence can be understood in terms of maximization of constraint satisfaction, in keeping with computational models that have had a substantial impact in cognitive ...
More
This chapter shows how epistemic coherence can be understood in terms of maximization of constraint satisfaction, in keeping with computational models that have had a substantial impact in cognitive science. It is shown how explanatory coherence subsumes Haack's recent “foundherentist” theory of knowledge. An account of deductive coherence is provided, showing how the selection of mathematical axioms can be understood as a constraint satisfaction problem. Visual interpretation can also be understood in terms of satisfaction of multiple constraints. After a brief account of how conceptual coherence can also be understood in terms of constraint satisfaction, the chapter concludes with a discussion of how the “multicoherence” theory of knowledge avoids many criticisms traditionally made of coherentism.Less
This chapter shows how epistemic coherence can be understood in terms of maximization of constraint satisfaction, in keeping with computational models that have had a substantial impact in cognitive science. It is shown how explanatory coherence subsumes Haack's recent “foundherentist” theory of knowledge. An account of deductive coherence is provided, showing how the selection of mathematical axioms can be understood as a constraint satisfaction problem. Visual interpretation can also be understood in terms of satisfaction of multiple constraints. After a brief account of how conceptual coherence can also be understood in terms of constraint satisfaction, the chapter concludes with a discussion of how the “multicoherence” theory of knowledge avoids many criticisms traditionally made of coherentism.
Pavol Hell and Jaroslav Nešetřil
- Published in print:
- 2004
- Published Online:
- September 2007
- ISBN:
- 9780198528173
- eISBN:
- 9780191713644
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198528173.003.0001
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics
This introductory chapter is a sampler of the material covered in the book. It introduces the notation and terminology in the book, and provides motivational examples and applications, many taken up ...
More
This introductory chapter is a sampler of the material covered in the book. It introduces the notation and terminology in the book, and provides motivational examples and applications, many taken up in more detail in later chapters. It gives the flavour of combinatorial aspects, algorithmic aspects, retractions, duality, constraint satisfaction problems, as well as structural properties of homomorphism composition. The highlights of this chapter include a simple proof of the Colouring Interpolation Theorem, a generalization of the No-Homomorphism Lemma, the construction of a triangle-free graph to which all cubic triangle-free graphs are homomorphic, a case of the Edge Reconstruction Conjecture, and a generalization of a theorem of Frucht on graphs with prescribed automorphism groups.Less
This introductory chapter is a sampler of the material covered in the book. It introduces the notation and terminology in the book, and provides motivational examples and applications, many taken up in more detail in later chapters. It gives the flavour of combinatorial aspects, algorithmic aspects, retractions, duality, constraint satisfaction problems, as well as structural properties of homomorphism composition. The highlights of this chapter include a simple proof of the Colouring Interpolation Theorem, a generalization of the No-Homomorphism Lemma, the construction of a triangle-free graph to which all cubic triangle-free graphs are homomorphic, a case of the Edge Reconstruction Conjecture, and a generalization of a theorem of Frucht on graphs with prescribed automorphism groups.
Marc Mézard and Andrea Montanari
- Published in print:
- 2009
- Published Online:
- September 2009
- ISBN:
- 9780198570837
- eISBN:
- 9780191718755
- Item type:
- book
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198570837.001.0001
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
This book presents a unified approach to a rich and rapidly evolving research domain at the interface between statistical physics, theoretical computer science/discrete mathematics, and ...
More
This book presents a unified approach to a rich and rapidly evolving research domain at the interface between statistical physics, theoretical computer science/discrete mathematics, and coding/information theory. The topics which have been selected, including spin glasses, error correcting codes, satisfiability, are central to each field. The approach focuses on the limit of large random instances, adopting a common formulation in terms of graphical models. It presents message passing algorithms like belief propagation and survey propagation, and their use in decoding and constraint satisfaction solving. It also explains analysis techniques like density evolution and the cavity method, and uses them to derive phase diagrams and study phase transitions.Less
This book presents a unified approach to a rich and rapidly evolving research domain at the interface between statistical physics, theoretical computer science/discrete mathematics, and coding/information theory. The topics which have been selected, including spin glasses, error correcting codes, satisfiability, are central to each field. The approach focuses on the limit of large random instances, adopting a common formulation in terms of graphical models. It presents message passing algorithms like belief propagation and survey propagation, and their use in decoding and constraint satisfaction solving. It also explains analysis techniques like density evolution and the cavity method, and uses them to derive phase diagrams and study phase transitions.
Dan Simon
- Published in print:
- 2010
- Published Online:
- May 2010
- ISBN:
- 9780195367584
- eISBN:
- 9780199776917
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780195367584.003.0009
- Subject:
- Psychology, Forensic Psychology
The Chapter deals with methodological constraints and possibilities in employing experimental psychology towards an understanding of judging. While acknowledging the concern with the ...
More
The Chapter deals with methodological constraints and possibilities in employing experimental psychology towards an understanding of judging. While acknowledging the concern with the external-validity of the research, the Chapter cautions against adopting measures that would compromise its construct-validity and thus muddy up the conclusions to be drawn from the findings. At the same time, scholars of judging ought to cast a wide net to employ whichever valid research that speaks to the diverse set of mental operations involved in judging. The field should not shy away from utilizing germane basic-psychological findings, as long as they withstand the rigorous demands of external-validity. It is proposed that the body of research on coherence based reasoning is one such example. In sum, the Chapter advocates a pedantic attention to the experimental design of the research coupled with open-mindedness to the range of useful and valid methodologies.Less
The Chapter deals with methodological constraints and possibilities in employing experimental psychology towards an understanding of judging. While acknowledging the concern with the external-validity of the research, the Chapter cautions against adopting measures that would compromise its construct-validity and thus muddy up the conclusions to be drawn from the findings. At the same time, scholars of judging ought to cast a wide net to employ whichever valid research that speaks to the diverse set of mental operations involved in judging. The field should not shy away from utilizing germane basic-psychological findings, as long as they withstand the rigorous demands of external-validity. It is proposed that the body of research on coherence based reasoning is one such example. In sum, the Chapter advocates a pedantic attention to the experimental design of the research coupled with open-mindedness to the range of useful and valid methodologies.
J. Levesque Hector
- Published in print:
- 2012
- Published Online:
- August 2013
- ISBN:
- 9780262016995
- eISBN:
- 9780262301411
- Item type:
- chapter
- Publisher:
- The MIT Press
- DOI:
- 10.7551/mitpress/9780262016995.003.0005
- Subject:
- Computer Science, Artificial Intelligence
This chapter describes five different constraint satisfaction problems. The first section introduces the idea of constraint satisfaction problems and presents a general way of solving them. Each of ...
More
This chapter describes five different constraint satisfaction problems. The first section introduces the idea of constraint satisfaction problems and presents a general way of solving them. Each of the five remaining sections takes on a different constraint satisfaction problem (Sudoku, cryptarithmetic, the eight-queens problem, logic problems, and scheduling) and shows how finding a solution can be cast as a computational task in Prolog.Less
This chapter describes five different constraint satisfaction problems. The first section introduces the idea of constraint satisfaction problems and presents a general way of solving them. Each of the five remaining sections takes on a different constraint satisfaction problem (Sudoku, cryptarithmetic, the eight-queens problem, logic problems, and scheduling) and shows how finding a solution can be cast as a computational task in Prolog.
Andreas Glöckner
- Published in print:
- 2008
- Published Online:
- May 2016
- ISBN:
- 9780262195805
- eISBN:
- 9780262272353
- Item type:
- chapter
- Publisher:
- The MIT Press
- DOI:
- 10.7551/mitpress/9780262195805.003.0012
- Subject:
- Psychology, Social Psychology
Classic behavioral decision research has intensively explored deliberate processes in decision making. Accordingly, individuals are viewed as bounded rational actors who, because of cognitive ...
More
Classic behavioral decision research has intensively explored deliberate processes in decision making. Accordingly, individuals are viewed as bounded rational actors who, because of cognitive limitations, use simple heuristics that are successful in certain environments. In this chapter, it is postulated that human cognitive capacity is less severely limited than has previously been assumed. When automatic processes are considered, one finds that cognitive capacity is not a binding constraint for many decision problems. The general parallel constraint satisfaction (PCS) approach is outlined, which aims at describing these automatic processes, and evidence supporting this approach is summarized. It is further argued, that in order to describe decision making comprehensively, models must account for the interaction between automatic and deliberate processes. The PCS rule is delineated which specifies this interaction. The model shifts the bounds of rationality considerably and has further evolutionary advantages. Implications for the efficient design of institutions are outlined. Finally, the German legal system is reviewed in terms of its ability to support efficient decision making by implementing many of the prescriptions derived from the PCS rule without explicit knowledge about the underlying processes.Less
Classic behavioral decision research has intensively explored deliberate processes in decision making. Accordingly, individuals are viewed as bounded rational actors who, because of cognitive limitations, use simple heuristics that are successful in certain environments. In this chapter, it is postulated that human cognitive capacity is less severely limited than has previously been assumed. When automatic processes are considered, one finds that cognitive capacity is not a binding constraint for many decision problems. The general parallel constraint satisfaction (PCS) approach is outlined, which aims at describing these automatic processes, and evidence supporting this approach is summarized. It is further argued, that in order to describe decision making comprehensively, models must account for the interaction between automatic and deliberate processes. The PCS rule is delineated which specifies this interaction. The model shifts the bounds of rationality considerably and has further evolutionary advantages. Implications for the efficient design of institutions are outlined. Finally, the German legal system is reviewed in terms of its ability to support efficient decision making by implementing many of the prescriptions derived from the PCS rule without explicit knowledge about the underlying processes.
J. Levesque Hector
- Published in print:
- 2012
- Published Online:
- August 2013
- ISBN:
- 9780262016995
- eISBN:
- 9780262301411
- Item type:
- chapter
- Publisher:
- The MIT Press
- DOI:
- 10.7551/mitpress/9780262016995.003.0006
- Subject:
- Computer Science, Artificial Intelligence
This chapter applies the idea of constraint satisfaction to a form of thinking that seems much more natural and relaxed: visual interpretation. This is a type of thinking that everyone can do to some ...
More
This chapter applies the idea of constraint satisfaction to a form of thinking that seems much more natural and relaxed: visual interpretation. This is a type of thinking that everyone can do to some extent, typically with a lot less conscious effort than puzzles require. The first section briefly considers the concept of vision and its connection to thinking. The following sections examine a sampling of three visual interpretation tasks: the interpretation of an image of a two-dimensional terrain as seen from above (Section 6.2); the interpretation of the edges in an image of three-dimensional polyhedral objects (Section 6.3); and recognizing objects of interest in an image (Section 6.4).Less
This chapter applies the idea of constraint satisfaction to a form of thinking that seems much more natural and relaxed: visual interpretation. This is a type of thinking that everyone can do to some extent, typically with a lot less conscious effort than puzzles require. The first section briefly considers the concept of vision and its connection to thinking. The following sections examine a sampling of three visual interpretation tasks: the interpretation of an image of a two-dimensional terrain as seen from above (Section 6.2); the interpretation of the edges in an image of three-dimensional polyhedral objects (Section 6.3); and recognizing objects of interest in an image (Section 6.4).
Florent Krzakala, Federico Ricci-Tersenghi, Lenka Zdeborova, Riccardo Zecchina, Eric W. Tramel, and Leticia F. Cugliandolo (eds)
- Published in print:
- 2015
- Published Online:
- March 2016
- ISBN:
- 9780198743736
- eISBN:
- 9780191803802
- Item type:
- book
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198743736.001.0001
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
This book contains a collection of the presentations that were given in October 2013 at the Les Houches Autumn School on statistical physics, optimization, inference, and message-passing algorithms. ...
More
This book contains a collection of the presentations that were given in October 2013 at the Les Houches Autumn School on statistical physics, optimization, inference, and message-passing algorithms. In the last decade, there has been increasing convergence of interest and methods between theoretical physics and fields as diverse as probability, machine learning, optimization, and inference problems. In particular, much theoretical and applied work in statistical physics and computer science has relied on the use of message-passing algorithms and their connection to the statistical physics of glasses and spin glasses. For example, both the replica and cavity methods have led to recent advances in compressed sensing, sparse estimation, and random constraint satisfaction, to name a few. This book’s detailed pedagogical lectures on statistical inference, computational complexity, the replica and cavity methods, and belief propagation are aimed particularly at PhD students, post-docs, and young researchers desiring the foundational material necessary for entering this rapidly developing field. In these lectures the reader can find detailed applications of theory to problems in community detection and clustering, signal denoising, identification of hidden cliques, error correcting codes, and constraint satisfaction.Less
This book contains a collection of the presentations that were given in October 2013 at the Les Houches Autumn School on statistical physics, optimization, inference, and message-passing algorithms. In the last decade, there has been increasing convergence of interest and methods between theoretical physics and fields as diverse as probability, machine learning, optimization, and inference problems. In particular, much theoretical and applied work in statistical physics and computer science has relied on the use of message-passing algorithms and their connection to the statistical physics of glasses and spin glasses. For example, both the replica and cavity methods have led to recent advances in compressed sensing, sparse estimation, and random constraint satisfaction, to name a few. This book’s detailed pedagogical lectures on statistical inference, computational complexity, the replica and cavity methods, and belief propagation are aimed particularly at PhD students, post-docs, and young researchers desiring the foundational material necessary for entering this rapidly developing field. In these lectures the reader can find detailed applications of theory to problems in community detection and clustering, signal denoising, identification of hidden cliques, error correcting codes, and constraint satisfaction.
Paul Thagard
- Published in print:
- 2019
- Published Online:
- February 2019
- ISBN:
- 9780190678715
- eISBN:
- 9780190686390
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780190678715.003.0002
- Subject:
- Psychology, Cognitive Models and Architectures
Brains make minds because mental representations and processes are performed by neural mechanisms. Mental representations work by patterns of firing in neural groups. More complicated representations ...
More
Brains make minds because mental representations and processes are performed by neural mechanisms. Mental representations work by patterns of firing in neural groups. More complicated representations that go beyond sensory experience can be formed by binding representations together, combining patterns of firing into new ones. In particular, binding can produce semantic pointers that coalesce and compress different kinds of information, including sensory, motor, emotional and verbal information. Semantic pointers retain connections to sensory and motor experience while also acquiring the autonomy that is usually attributed to symbols. Eliasmith’s semantic pointer hypothesis shows how neural cells can interact to produce high-level thinking. Different representations compete with each other to provide accounts of what is going on in the world through a parallel process of satisfaction of multiple constraints. Neural networks can learn by changing the synaptic connections between neurons.Less
Brains make minds because mental representations and processes are performed by neural mechanisms. Mental representations work by patterns of firing in neural groups. More complicated representations that go beyond sensory experience can be formed by binding representations together, combining patterns of firing into new ones. In particular, binding can produce semantic pointers that coalesce and compress different kinds of information, including sensory, motor, emotional and verbal information. Semantic pointers retain connections to sensory and motor experience while also acquiring the autonomy that is usually attributed to symbols. Eliasmith’s semantic pointer hypothesis shows how neural cells can interact to produce high-level thinking. Different representations compete with each other to provide accounts of what is going on in the world through a parallel process of satisfaction of multiple constraints. Neural networks can learn by changing the synaptic connections between neurons.
Marc Mézard
- Published in print:
- 2015
- Published Online:
- March 2016
- ISBN:
- 9780198743736
- eISBN:
- 9780191803802
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198743736.003.0004
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
The cavity method is introduced as a heuristic framework from a physics perspective to solve probabilistic graphical models and is presented at both the replica symmetry (RS) and one-step replica ...
More
The cavity method is introduced as a heuristic framework from a physics perspective to solve probabilistic graphical models and is presented at both the replica symmetry (RS) and one-step replica symmetry breaking (1RSB) levels. This technique has been applied with success to a wide range of models and problems, such as spin glasses, random constraint satisfaction problems (rCSP), and error correcting codes. First, the RS cavity solution for the Sherrington–Kirkpatrick model—a fully connected spin glass model—is derived and its equivalence to the RS solution obtained using replicas is discussed. The general cavity method for diluted graphs is then illustrated at both RS and 1RSB levels. The latter was a significant breakthrough in the last decade and has direct applications to rCSP. Finally, as an example of an actual problem, k-SAT is investigated using belief and survey propagation.Less
The cavity method is introduced as a heuristic framework from a physics perspective to solve probabilistic graphical models and is presented at both the replica symmetry (RS) and one-step replica symmetry breaking (1RSB) levels. This technique has been applied with success to a wide range of models and problems, such as spin glasses, random constraint satisfaction problems (rCSP), and error correcting codes. First, the RS cavity solution for the Sherrington–Kirkpatrick model—a fully connected spin glass model—is derived and its equivalence to the RS solution obtained using replicas is discussed. The general cavity method for diluted graphs is then illustrated at both RS and 1RSB levels. The latter was a significant breakthrough in the last decade and has direct applications to rCSP. Finally, as an example of an actual problem, k-SAT is investigated using belief and survey propagation.
