This paper gives a brief survey of current research on the complexity of the constraint satisfaction problem over fixed constraint languages.

We investigate the complexity of finding solutions to infinite recursive constraint satisfaction problems. We show that, in general, the problem of finding a solution to an infinite recursive constraint satisfaction problem is equivalent to the problem of finding an infinite path through a recursive tree. We also identify natural classes of infinite recursive constraint satisfaction problems where the problem of finding a solution to the infinite recursive constraint satisfaction (...) problem is equivalent to the problem of finding an infinite path through finitely branching recursive trees or recursive binary trees. There are a large number of results in the literature on the complexity of the problem of finding an infinite path through a recursive tree. Our main result allows us to automatically transfer such results to give equivalent results about the complexity of the problem of finding a solution to a recursive constraint satisfaction problem. (shrink)

There exist two conjectures for constraint satisfaction problems of reducts of finitely bounded homogeneous structures: the first one states that tractability of the CSP of such a structure is, when the structure is a model-complete core, equivalent to its polymorphism clone satisfying a certain nontrivial linear identity modulo outer embeddings. The second conjecture, challenging the approach via model-complete cores by reflections, states that tractability is equivalent to the linear identities satisfied by its polymorphisms clone, together with the natural (...) uniformity on it, being nontrivial. We prove that the identities satisfied in the polymorphism clone of a structure allow for conclusions about the orbit growth of its automorphism group, and apply this to show that the two conjectures are equivalent. We contrast this with a counterexample showing that [Formula: see text]-categoricity alone is insufficient to imply the equivalence of the two conditions above in a model-complete core. Taking another approach, we then show how the Ramsey property of a homogeneous structure can be utilized for obtaining a similar equivalence under different conditions. We then prove that any polymorphism of sufficiently large arity which is totally symmetric modulo outer embeddings of a finitely bounded structure can be turned into a nontrivial system of linear identities, and obtain nontrivial linear identities for all tractable cases of reducts of the rational order, the random graph, and the random poset. Finally, we provide a new and short proof, in the language of monoids, of the theorem stating that every [Formula: see text]-categorical structure is homomorphically equivalent to a model-complete core. (shrink)

We observe a number of connections between recent developments in the study of constraint satisfaction problems, irredundant axiomatisation and the study of topological quasivarieties. Several restricted forms of a conjecture of Clark, Davey, Jackson and Pitkethly are solved: for example we show that if, for a finite relational structure M, the class of M-colourable structures has no finite axiomatisation in first order logic, then there is no set (even infinite) of first order sentences characterising the continuously M-colourable structures (...) amongst compact totally disconnected relational structures. We also refute a rather old conjecture of Gorbunov by presenting a finite structure with an infinite irredundant quasi-identity basis. (shrink)

A theory of analogical mapping between source and target analogs based upon interacting structural, semantic, and pragmatic constraints is proposed here. The structural constraint of isomorphism encourages mappings that maximize the consistency of relational corresondences between the elements of the two analogs. The constraint of semantic similarity supports mapping hypotheses to the degree that mapped predicates have similar meanings. The constraint of pragmatic centrality favors mappings involving elements the analogist believes to be important in order to achieve (...) the purpose for which the analogy is being used. The theory is implemented in a computer program called ACME (Analogical Constraint Mapping Engine), which represents constraints by means of a network of supporting and competing hypotheses regarding what elements to map. A cooperative algorithm for parallel constraint satisfaction identities mapping hypotheses that collectively represent the overall mapping that best fits the interacting constraints. ACME has been applied to a wide range of examples that include problem analogies, analogical arguments, explanatory analogies, story analogies, formal analogies, and metaphors. ACME is sensitive to semantic and pragmatic information if it is available, and yet able to compute mappings between formally isomorphic analogs without any similar or identical elements. The theory is able to account for empirical findings regarding the impact of consistency and similarity on human processing of analogies. (shrink)

Journal of Mathematical Logic, Ahead of Print.

This paper provides a computational characterization of coherence that applies to a wide range of philosophical problems and psychological phenomena. Maximizing coherence is a matter of maximizing satisfaction of a set of positive and negative constraints. After comparing five algorithms for maximizing coherence, we show how our characterization of coherence overcomes traditional philosophical objections about circularity and truth.

In Wason’s Selection Task, subjects: process information from the instructions and build a mental representation of the problem, then: select a course of action to solve the problem,under the constraints imposed by the instructions. We analyze both aspects as part of a constraint satisfaction problem without assuming Wason’s ‘logical’ solution to be the correct one. We show that outcome of step may induce mutually inconsistent constraints, causing subjects to select at step solutions that violate some (...) of them. Our analysis explains why inconsistent constraints are less likely disrupt non-abstract versions of the tasks, but unlike Bayesians does not posit different mechanisms in abstract and thematic variants. We then assess the logicality of the task, and conclude on cognitive tasks as coordination problems. (shrink)

In a seminal 1977 article, Rumelhart argued that perception required the simultaneous use of multiple sources of information, allowing perceivers to optimally interpret sensory information at many levels of representation in real time as information arrives. Building on Rumelhart's arguments, we present the Interactive Activation hypothesis—the idea that the mechanism used in perception and comprehension to achieve these feats exploits an interactive activation process implemented through the bidirectional propagation of activation among simple processing units. We then examine the interactive activation (...) model of letter and word perception and the TRACE model of speech perception, as early attempts to explore this hypothesis, and review the experimental evidence relevant to their assumptions and predictions. We consider how well these models address the computational challenge posed by the problem of perception, and we consider how consistent they are with evidence from behavioral experiments. We examine empirical and theoretical controversies surrounding the idea of interactive processing, including a controversy that swirls around the relationship between interactive computation and optimal Bayesian inference. Some of the implementation details of early versions of interactive activation models caused deviation from optimality and from aspects of human performance data. More recent versions of these models, however, overcome these deficiencies. Among these is a model called the multinomial interactive activation model, which explicitly links interactive activation and Bayesian computations. We also review evidence from neurophysiological and neuroimaging studies supporting the view that interactive processing is a characteristic of the perceptual processing machinery in the brain. In sum, we argue that a computational analysis, as well as behavioral and neuroscience evidence, all support the Interactive Activation hypothesis. The evidence suggests that contemporary versions of models based on the idea of interactive activation continue to provide a basis for efforts to achieve a fuller understanding of the process of perception. (shrink)

Motivated by constraint satisfaction problems, Feder and Vardi (SIAM Journal of Computing, 28, 57–104, 1998) set out to search for fragments of satisfying the dichotomy property: every problem definable in is either in P or else NP-complete. Feder and Vardi considered in this connection two logics, strict NP (or SNP) and monadic, monotone, strict NP without inequalities (or MMSNP). The former consists of formulas of the form , where is a quantifier-free formula in a relational vocabulary; and (...) the latter is the fragment of SNP whose formulas involve only negative occurrences of relation symbols, only monadic second-order quantifiers, and no occurrences of the equality symbol. It remains an open problem whether MMSNP enjoys the dichotomy property. In the present paper, SNP and MMSNP are characterized in terms of partially ordered connectives. More specifically, SNP is characterized using the logic D of partially ordered connectives introduced in Blass and Gurevich (Annals of Pure and Applied Logic, 32, 1–16, 1986), Sandu and Väänänen (Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 38, 361–372 1992), and MMSNP employing a generalization C of D introduced in the present paper. (shrink)

Model RB is a model of random constraint satisfaction problems, which exhibits exact satisfiability phase transition and many hard instances, both experimentally and theoretically. Benchmarks based on Model RB have been successfully used by various international algorithm competitions and many research papers. In a previous work, Xu and Li defined two notions called i-constraint assignment tuple and flawed i-constraint assignment tuple to show an exponential resolution complexity of Model RB. These two notions are similar to some (...) kind of consistency in constraint satisfaction problems, but seem different from all kinds of consistency so far known in literatures. In this paper, we explicitly define this kind of consistency, called variable-centered consistency, and show an upper bound on a parameter in Model RB, such that up to this bound the typical instances of Model RB are variable-centered consistent. (shrink)

We give a new and elementary construction of primitive positive decomposition of higher arity relations into binary relations on finite domains. Such decompositions come up in applications to constraint satisfaction problems, clone theory and relational databases. The construction exploits functional completeness of 2-input functions in many-valued logic by interpreting relations as graphs of partially defined multivalued ‘functions’. The ‘functions’ are then composed from ordinary functions in the usual sense. The construction is computationally effective and relies on well-developed methods (...) of functional decomposition, but reduces relations only to ternary relations. An additional construction then decomposes ternary into binary relations, also effectively, by converting certain disjunctions into existential quantifications. The result gives a uniform proof of Peirce’s reduction thesis on finite domains, and shows that the graph of any Sheffer function composes all relations there. (shrink)

Estimation of Distribution Algorithms, which employ probabilistic models to generate the next population, are new promising methods in the field of genetic and evolutionary algorithms. In the case of conventional Genetic and Evolutionary Algorithms are applied to Constraint Satisfaction Problems, it is well-known that the incorporation of the domain knowledge in the Constraint Satisfaction Problems is quite effective. In this paper, we constitute a memetic algorithm as a combination of the Estimation of Distribution Algorithm and a (...) repair method. Experimental results on general Constraint Satisfaction Problems tell us the effectiveness of the proposed method. (shrink)

Many stochastic search algorithms have recently been developed to make more remarkable progress than systematic search algorithms because stochastic algorithms sometimes solve large-scale constraint satisfaction problems in a practical time. However, such stochastic algorithms have the drawback of getting stuck in local optima which are not acceptable as final solutions. We analyze an iterative improvement algorithm from the viewpoint of constraint structures causing local optima. Using the graph-coloring problem with three colors, an archetype problem to (...) evaluate constraint satisfaction algorithms, we study the local graph structures around which so many conflicts thrash. We propose a key constraint structure, an LM pair, which may induce a local optimum, and clarify the mechanism of how conflicting colors for an LM pair obstruct the stepwise refinement of hill-climbing. Experimental results show that LM pairs are strongly correlated with the search efficiency of the stochastic search algorithm. (shrink)

The field service scheduling problem is the key problem in field services. Field service pays particular attention to customer experience, that is, customer satisfaction. Customer satisfaction described by customer behavior characteristics based on the prospect theory is considered as the primary optimization goal in this paper. The knowledge of the insertion feasibility on the solution is analysed based on the skill constraint and time window. According to the knowledge, an initialization method based on the nearest (...) heuristic algorithm is constructed. Based on the prior knowledge of the FSSP and the endowment of the Fruit Fly Optimization Algorithm, two operators are defined according to the matrix encoding method. Based on these two operators, three search strategies are then proposed, and the smell-based search strategy and vision-based search strategy for the FOA are redesigned. To verify the performance of the algorithms, the proposed operators and strategies are tested and analysed in the well-known benchmark. Through comparison with the state-of-the-art algorithms, the results show that the proposed HFOA is an effective and efficient method to solve the FSSP with customer satisfaction. (shrink)

We consider a special case of heuristics, namely numeric heuristic evaluation functions, and their use in artificial intelligence search algorithms. The problems they are applied to fall into three general classes: single-agent path-finding problems, two-player games, and constraint-satisfaction problems. In a single-agent path-finding problem, such as the Fifteen Puzzle or the travelling salesman problem, a single agent searches for a shortest path from an initial state to a goal state. Two-player games, such as chess and checkers, (...) involve an adversarial relationship between two players, each trying to win the game. In a constraint-satisfaction, problem, such as the 8-Queens problem, the task is to find a state that satisfies a set of constraints. All of these problems are computationally intensive, and heuristic evaluation functions are used to reduce the amount of computation required to solve them. In each case we explain the nature of the evaluation functions used, how they are used in search algorithms, and how they can be automatically learned or acquired. (shrink)

Most of real world problems contain complex and various constraints, and the penalty depending on the degree of violation is often used to handle them. However, two objectives, to reduce the violation and to optimize the primary value, are inherently oppositive. Therefore, using additive penalty method often leads the fatal compromise to a solution with bad primary objective value in return for no violation. In this paper, we employ separated constraint satisfaction, to deal these two objectives independently like (...) as a multi-objective optimization. The efficiency of SCS is shown on a simple benchmark and the sewerage system control problem. (shrink)

This target article presents a new computational theory of explanatory coherence that applies to the acceptance and rejection of scientific hypotheses as well as to reasoning in everyday life, The theory consists of seven principles that establish relations of local coherence between a hypothesis and other propositions. A hypothesis coheres with propositions that it explains, or that explain it, or that participate with it in explaining other propositions, or that offer analogous explanations. Propositions are incoherent with each other if they (...) are contradictory, Propositions that describe the results of observation have a degree of acceptability on their own. An explanatory hypothesis is acccpted if it coheres better overall than its competitors. The power of the seven principles is shown by their implementation in a connectionist program called ECHO, which treats hypothesis evaluation as a constraint satisfaction problem. Inputs about the explanatory relations are used to create a network of units representing propositions, while coherende and incoherence relations are encoded by excitatory and inbihitory links. ECHO provides an algorithm for smoothly integrating theory evaluation based on considerations of explanatory breadth, simplicity, and analogy. It has been applied to such important scientific cases as Lovoisier's argument for oxygen against the phlogiston theory and Darwin's argument for evolution against creationism, and also to cases of legal reasoning. The theory of explanatory coherence has implications for artificial intelligence, psychology, and philosophy. (shrink)

I propose a conceptual framework for emotions according to which they are best understood as the feedback mechanism a creature possesses in virtue of its function to learn. More specifically, emotions can be neatly modeled as a measure of harmony in a certain kind of constraint satisfaction problem. This measure can be used as error for weight adjustment (learning) in an unsupervised connectionist network.

In this article, we investigate the status of the homomorphism preservation property amongst restricted classes of finite relational structures and algebraic structures. We show that there are many homomorphism-closed classes of finite lattices that are definable by a first-order sentence but not by existential positive sentences, demonstrating the failure of the homomorphism preservation property for lattices at the finite level. In contrast to the negative results for algebras, we establish a finite-level relativised homomorphism preservation theorem in the relational case. More (...) specifically, we give a complete finite-level characterisation of first-order definable finitely generated anti-varieties relative to classes of relational structures definable by sentences of some general forms. When relativisation is dropped, this gives a fresh proof of Atserias’s characterisation of first-order definable constraint satisfaction problems over a fixed template, a well known special case of Rossman’s Finite Homomorphism Preservation Theorem. (shrink)

The year 2012 has witnessed worldwide celebrations of Alan Turing’s 100th birthday. A great number of conferences and workshops were organized by logicians, computer scientists and researchers in AI, showing the continued flourishing of computer science, and the fruitful interfaces between logic and computer science. Logic is no longer just the concept that Frege had about one hundred years ago, let alone that of Aristotle twenty centuries before. One of the prominent features of contemporary logic is its interdisciplinary character, connecting (...) across mathematics, philosophy, modern computer science, and even the cognitive and social sciences. -/- China is no exception. This special issue explores interfaces of logic with AI and other disciplines, and it attempts to give a bird’s eye view of the developing landscape of logic and AI in China. Our contributors come from computer science, AI, philosophy and linguistics, united by their interest in using formal logical tools and notions to deal with substantial problems in their fields. We are aware that AI is a vast area, and that the limitations of space in a volume like this may provide a somewhat incomplete or biased view. Still we hope that the six papers selected here illustrate the concerns and curiosity driving Chinese researchers, on topics shared with our colleagues around the world. -/- One of the active research areas in AI is planning under uncertainty, with incomplete knowledge, where a well-established logical framework is the action language of Son and Baral (Son and Baral 2001). This language can express the notions of sensing actions and making conditional plans. However, its current semantics is not yet satisfactory, since according to the semantics an agent would not have knowledge of what happens after a plan is executed, which can be a serious problem in a safety-critical environment. In their paper Proof Systems for Planning under Cautious Semantics (Shen and Zhao 2013), Yuping Shen and Xishun Zhao address this problem and propose a cautious and weakly cautious semantics for the action language. This new semantics enables the agent to know exactly what happens after executing an action. Hoare style proof systems are then proposed and proved to be sound and complete. What is more, the proposed new system reduces the reasoning complexity of the action language. -/- In Preferential Semantics for Plausible Subsumption in Possibility Theory (Qi and Zhang 2013), Guilin Qi and Zhizheng Zhang investigate another important issue in AI: how to handle exceptions in a knowledge-based system. This has become a hot topic in recent years, especially in ontological design, where description logics are widely used. The question then arises whether we can get a nonmonotonic extension of description logic. To answer this, the authors first propose three preferential semantics for plausible subsumption in the framework of possibility theory (Dubois and Prade 1985) and study their properties and their relationships. Then they introduce preferential subsumptions to a description logic-based knowledge system, and define an entailment relation of plausible subsumption. Moreover, they study reductions of the new semantics to standard semantics for an expressive description logic. -/- Counterfactual reasoning has been explored extensively by philosophers, cf. Lewis (1973), Stalnaker (1968). But in the last two decades, causal models have been proposed for modeling counterfactual reasoning by researchers in AI. In A Lewisian Logic of Causal Counterfactuals (Zhang 2013), Jiji Zhang studies classes of causal models and provides formal characterizations. In particular, a new logic system is proposed and proved complete for the class of ‘Lewisian models’ satisfying all the principles of David Lewis’s logic of counterfactuals. Moreover, Zhang compares his new framework with those of Lewis and Stalnaker, and also establishes formal connections with more recent approaches by Galles and Pearl, and by Halpern. -/- Consistency is a fundamental notion in logic, but it also plays a key role in many techniques for solving constraint satisfaction problems (Mackworth 1977). In Variable-Centered Consistency in Model RB (Li et al. 2013), Liang Li, Tian Liu and Ke Xu start with a discussion of i-consistency in ‘Model RB’ and ‘Model RD’, two models of random constraint satisfaction problems with growing domain size, then compare it with the notion of t-consistency and strong t-consistency in well-known earlier work by Freuder. After that, the authors define a new kind of variable-centered consistency, and show an upper bound on a suitably chosen parameter in Model RB and Model RD, such that up to this bound, all typical instances of Model RB are variable-centered consistent. -/- Language understanding is a cognitive process that human beings carry out every day. Metaphor is a pervasive phenomenon in natural languages, and its cognitive role calls for interpretation. There is a growing body of literature on cognitive mechanisms underlying metaphor. The paper An Ontology-Based Approach to Metaphor Cognitive Computation (Huang et al. 2013) by Xiaoxi Huang, Huaxin Huang, Beishui Liao, and Cihua Xu proposes a theoretical framework for metaphor understanding based on recent results from cognitive science (Shutova 2010). They then introduce ontology as a knowledge representation method, and present a new ontological model to formalize metaphor-based knowledge. An algorithmic description is provided using a quantitative measure of integrated degree, and its effectiveness is demonstrated. -/- Puzzles and their solution mechanisms are a recurrent theme in many fields. Dynamic epistemic logic (van Ditmarsch et al. 2007); (van Benthem 2011) is a recent framework that can handle information dynamics in knowledge puzzles. In Reasoning About Agent Types and the Hardest Logic Puzzle Ever (Liu and Wang 2013), Fenrong Liu and Yanjing Wang propose a new dynamic-epistemic logic that can specify different types of agents and analyse agents’ knowledge, communication and reasoning. To demonstrate its power, Smullyan’s well-known Knights and Knaves puzzles are formalized, as well as the Hardest Logic Puzzle Ever (HLPE) of Boolos (Boolos 1996). Moreover, a spectrum of new puzzles is found involving knowledge-based agent types, and their solution complexity is shown to be harder than that for existing logic puzzles. It is also shown that a version of HLPE in which the agents do not know the others’ types does not have a solution at all. -/- Finally, we would like to thank the editor of Minds and Machines, Gregory Wheeler, for his efficient assistance and kind support. We also thank Ties Nijssen at Springer for his encouragement to start this project at the first place. And of course, our appreciation goes to our authors, as well as all the colleagues who have helped us review the papers in this collection. (shrink)

This book gives a comprehensive overview of central themes of finite model theory – expressive power, descriptive complexity, and zero-one laws – together with selected applications relating to database theory and artificial intelligence, especially constraint databases and constraint satisfaction problems. The final chapter provides a concise modern introduction to modal logic, emphasizing the continuity in spirit and technique with finite model theory. This underlying spirit involves the use of various fragments of and hierarchies within first-order, second-order, fixed-point, (...) and infinitary logics to gain insight into phenomena in complexity theory and combinatorics. The book emphasizes the use of combinatorial games, such as extensions and refinements of the Ehrenfeucht-Fraissé pebble game, as a powerful way to analyze the expressive power of such logics, and illustrates how deep notions from model theory and combinatorics, such as o-minimality and treewidth, arise naturally in the application of finite model theory to database theory and AI. Students of logic and computer science will find here the tools necessary to embark on research into finite model theory, and all readers will experience the excitement of a vibrant area of the application of logic to computer science. (shrink)

Sieg has proposed axioms for computability whose models can be reduced to Turing machines. This lecture will investigate to what extent these axioms hold for reasoning. In particular we focus on the requirement that the configurations that a computing agent (whether human or machine) operates on must be ’immediately recognisable’. If one thinks of reasoning as derivation in a calculus, this requirement is satisfied; but even in contexts which are only slightly less formal, the requirement cannot be met. Our main (...) example will be the Wason selection task, a propositional reasoning task in which in a typical (undergraduate) subject group only around 5% arrive at the answer dictated by classical logic. The instructions for this task (as well as other standard tasks in the psychology of reasoning, such as syllogisms) do not contain any ’immediately recognisable’ configurations. The subject must try to find an interpretation of the task by making the various elements in the instructions cohere, in effect solving a difficult constraint satisfaction problem, which has no unique solution. The subject has given a complete interpretation of the task if she can formulate the problem posed in the task as a theorem to be proved. The complexity of such theorems can be quite high; e.g. for the propositional Wason selection task the theorem can be in Σ1 3 . This sounds implausible, but we’ll present experimental data confirming this point. (shrink)