Results for 'constraint satisfaction problem'

979 found
Order:
  1.  21
    The Constraint Satisfaction Problem and Universal Algebra.Libor Barto - 2015 - Bulletin of Symbolic Logic 21 (3):319-337.
    This paper gives a brief survey of current research on the complexity of the constraint satisfaction problem over fixed constraint languages.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  2.  42
    The complexity of recursive constraint satisfaction problems.Victor W. Marek & Jeffrey B. Remmel - 2010 - Annals of Pure and Applied Logic 161 (3):447-457.
    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 (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  3.  25
    Decomposing constraint satisfaction problems using database techniques.Marc Gyssens, Peter G. Jeavons & David A. Cohen - 1994 - Artificial Intelligence 66 (1):57-89.
  4.  17
    Qualitative constraint satisfaction problems: An extended framework with landmarks.Sanjiang Li, Weiming Liu & Shengsheng Wang - 2013 - Artificial Intelligence 201 (C):32-58.
  5.  19
    Constraint satisfaction problem with bilevel constraint: application to interpretation of over-segmented images.A. Deruyver & Y. Hodé - 1997 - Artificial Intelligence 93 (1-2):321-335.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  6.  14
    Compiling constraint satisfaction problems.Rainer Weigel & Boi Faltings - 1999 - Artificial Intelligence 115 (2):257-287.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  7.  19
    Network-based heuristics for constraint-satisfaction problems.Rina Dechter & Judea Pearl - 1987 - Artificial Intelligence 34 (1):1-38.
  8.  34
    Equations in oligomorphic clones and the constraint satisfaction problem for ω-categorical structures.Libor Barto, Michael Kompatscher, Miroslav Olšák, Trung Van Pham & Michael Pinsker - 2019 - Journal of Mathematical Logic 19 (2):1950010.
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  9.  45
    Constraint Satisfaction, Irredundant Axiomatisability and Continuous Colouring.Marcel Jackson & Belinda Trotta - 2013 - Studia Logica 101 (1):65-94.
    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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  10.  18
    Domain permutation reduction for constraint satisfaction problems.Martin J. Green & David A. Cohen - 2008 - Artificial Intelligence 172 (8-9):1094-1118.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  11.  20
    Solving quantified constraint satisfaction problems.Ian P. Gent, Peter Nightingale, Andrew Rowley & Kostas Stergiou - 2008 - Artificial Intelligence 172 (6-7):738-771.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  12.  16
    Backjump-based backtracking for constraint satisfaction problems.Rina Dechter & Daniel Frost - 2002 - Artificial Intelligence 136 (2):147-188.
  13.  17
    Automated streamliner portfolios for constraint satisfaction problems.Patrick Spracklen, Nguyen Dang, Özgür Akgün & Ian Miguel - 2023 - Artificial Intelligence 319 (C):103915.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  14.  18
    The complexity of constraint satisfaction problems for small relation algebras.M. Cristani & R. Hirsch - 2004 - Artificial Intelligence 156 (2):177-196.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  15.  15
    The complexity of some polynomial network consistency algorithms for constraint satisfaction problems.Alan K. Mackworth & Eugene C. Freuder - 1985 - Artificial Intelligence 25 (1):65-74.
  16.  15
    Increasing tree search efficiency for constraint satisfaction problems.Robert M. Haralick & Gordon L. Elliott - 1980 - Artificial Intelligence 14 (3):263-313.
  17.  15
    An empirical study of phase transitions in binary constraint satisfaction problems.Patrick Prosser - 1996 - Artificial Intelligence 81 (1-2):81-109.
  18.  13
    Experimental evaluation of preprocessing algorithms for constraint satisfaction problems.Rina Dechter & Itay Meiri - 1994 - Artificial Intelligence 68 (2):211-241.
  19.  20
    Locating the phase transition in binary constraint satisfaction problems.Barbara M. Smith & Martin E. Dyer - 1996 - Artificial Intelligence 81 (1-2):155-181.
  20.  75
    Analogical Mapping by Constraint Satisfaction.Keith J. Holyoak & Paul Thagard - 1989 - Cognitive Science 13 (3):295-355.
    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 (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   267 citations  
  21.  15
    Backtracking techniques for the job shop scheduling constraint satisfaction problem.Norman Sadeh, Katia Sycara & Yalin Xiong - 1995 - Artificial Intelligence 76 (1-2):455-480.
  22.  18
    Broken triangles: From value merging to a tractable class of general-arity constraint satisfaction problems.Martin C. Cooper, Aymeric Duchein, Achref El Mouelhi, Guillaume Escamocher, Cyril Terrioux & Bruno Zanuttini - 2016 - Artificial Intelligence 234 (C):196-218.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  23.  16
    A framework for step-wise explaining how to solve constraint satisfaction problems.Bart Bogaerts, Emilio Gamba & Tias Guns - 2021 - Artificial Intelligence 300 (C):103550.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  24.  22
    On the phase transitions of random k-constraint satisfaction problems.Yun Fan & Jing Shen - 2011 - Artificial Intelligence 175 (3-4):914-927.
  25.  12
    Variable and value ordering heuristics for the job shop scheduling constraint satisfaction problem.Norman Sadeh & Mark S. Fox - 1996 - Artificial Intelligence 86 (1):1-41.
  26.  22
    Reordering all agents in asynchronous backtracking for distributed constraint satisfaction problems.Younes Mechqrane, Mohamed Wahbi, Christian Bessiere & Kenneth N. Brown - 2020 - Artificial Intelligence 278 (C):103169.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  27.  41
    Branch and bound algorithms to solve semiring constraint satisfaction problems.Louise Leenen & Aditya Ghose - 2008 - In Tu-Bao Ho & Zhi-Hua Zhou, PRICAI 2008: Trends in Artificial Intelligence. Springer. pp. 991--997.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark  
  28.  19
    An optimal backtrack algorithm for tree-structured constraint satisfaction problems.Roberto J. Bayardo & Daniel P. Miranker - 1994 - Artificial Intelligence 71 (1):159-181.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  29.  10
    Skypattern mining: From pattern condensed representations to dynamic constraint satisfaction problems.Willy Ugarte, Patrice Boizumault, Bruno Crémilleux, Alban Lepailleur, Samir Loudni, Marc Plantevit, Chedy Raïssi & Arnaud Soulet - 2017 - Artificial Intelligence 244 (C):48-69.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  30.  20
    Erratum: Equations in oligomorphic clones and the constraint satisfaction problem for ω-categorical structures.Libor Barto, Michael Kompatscher, Miroslav Olšák, Trung Van Pham & Michael Pinsker - 2021 - Journal of Mathematical Logic 21 (2):2192001.
    Journal of Mathematical Logic, Ahead of Print.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  31.  29
    A general model and thresholds for random constraint satisfaction problems.Yun Fan, Jing Shen & Ke Xu - 2012 - Artificial Intelligence 193 (C):1-17.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  32.  12
    Fundamental properties of neighbourhood substitution in constraint satisfaction problems.Martin C. Cooper - 1997 - Artificial Intelligence 90 (1-2):1-24.
  33.  15
    Information Processing and Constraint Satisfaction in Wason’s Selection Task.Emmanuel Genot - 2012 - In Jesus M. Larrazabal, Cognition, reasoning, emotion, Action. CogSc-12. Proceedings of the ILCLI International Workshop on Cognitive Science. pp. 153-162.
    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 (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  34.  60
    Coherence as Constraint Satisfaction.Paul Thagard & Karsten Verbeurgt - 1998 - Cognitive Science 22 (1):1-24.
    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.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   91 citations  
  35.  63
    Interactive Activation and Mutual Constraint Satisfaction in Perception and Cognition.James L. McClelland, Daniel Mirman, Donald J. Bolger & Pranav Khaitan - 2014 - Cognitive Science 38 (6):1139-1189.
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   19 citations  
  36.  10
    Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems.Steven Minton, Mark D. Johnston, Andrew B. Philips & Philip Laird - 1992 - Artificial Intelligence 58 (1-3):161-205.
  37.  56
    Partially ordered connectives and monadic monotone strict np.Lauri Hella, Merlijn Sevenster & Tero Tulenheimo - 2008 - Journal of Logic, Language and Information 17 (3):323-344.
    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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  38. Variable-Centered Consistency in Model RB.Liang Li, Tian Liu & Ke Xu - 2013 - Minds and Machines 23 (1):95-103.
    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 (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  39. Functional completeness and primitive positive decomposition of relations on finite domains.Sergiy Koshkin - 2024 - Logic Journal of the IGPL 32.
    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 (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  40.  34
    分布推定アルゴリズムによる Memetic Algorithms を用いた制約充足問題解決.Handa Hisashi - 2004 - Transactions of the Japanese Society for Artificial Intelligence 19:405-412.
    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 (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  41.  19
    確率的制約充足アルゴリズムにおける局所最適構造.西原 清一 水野 一徳 - 2001 - Transactions of the Japanese Society for Artificial Intelligence 16:38-45.
    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 (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  42.  19
    Knowledge and Behavior-Driven Fruit Fly Optimization Algorithm for Field Service Scheduling Problem with Customer Satisfaction.Bin Wu, Hui-Jun Jiang, Chao Wang & Min Dong - 2021 - Complexity 2021:1-14.
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  43.  80
    Heuristic evaluation functions in artificial intelligence search algorithms.Richard E. Korf - 1995 - Minds and Machines 5 (4):489-498.
    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, (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  44. Explanatory coherence (plus commentary).Paul Thagard - 1989 - Behavioral and Brain Sciences 12 (3):435-467.
    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 (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   246 citations  
  45.  16
    独立制約充足による最適化と送水制御への適用.青木 圭 池田 心 - 2004 - Transactions of the Japanese Society for Artificial Intelligence 19:38-46.
    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 (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  46.  21
    Relativised Homomorphism Preservation at the Finite Level.Lucy Ham - 2017 - Studia Logica 105 (4):761-786.
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  47. Functions, creatures, learning, emotion.Stephen Petersen - 2004 - Hudlicka and Canamero.
    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.
     
    Export citation  
     
    Bookmark  
  48. Functions, Creatures, Learning, Emotion.Angell Hall - unknown
    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.
     
    Export citation  
     
    Bookmark  
  49.  17
    Algebra and computer science.Delaram Kahrobaei, Bren Cavallo & David Garber (eds.) - 2016 - Providence, Rhode Island: American Mathematical Society.
    This volume contains the proceedings of three special sessions: Algebra and Computer Science, held during the Joint AMS-EMS-SPM meeting in Porto, Portugal, June 10–13, 2015; Groups, Algorithms, and Cryptography, held during the Joint Mathematics Meeting in San Antonio, TX, January 10–13, 2015; and Applications of Algebra to Cryptography, held during the Joint AMS-Israel Mathematical Union meeting in Tel-Aviv, Israel, June 16–19, 2014. Papers contained in this volume address a wide range of topics, from theoretical aspects of algebra, namely group theory, (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  50.  78
    Finite Model Theory and its Applications.Erich Grädel, Phokion Kolaitis, Libkin G., Marx Leonid, Spencer Maarten, Vardi Joel, Y. Moshe, Yde Venema & Scott Weinstein - 2007 - Springer.
    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, (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
1 — 50 / 979