Open Access. Powered by Scholars. Published by Universities.®

Computer Engineering Commons

Open Access. Powered by Scholars. Published by Universities.®

Computer Science and Engineering: Theses, Dissertations, and Student Research

Consistency

Publication Year

Articles 1 - 2 of 2

Full-Text Articles in Computer Engineering

Higher-Level Consistencies: Where, When, And How Much, Robert J. Woodward Sep 2018

Higher-Level Consistencies: Where, When, And How Much, Robert J. Woodward

Computer Science and Engineering: Theses, Dissertations, and Student Research

Determining whether or not a Constraint Satisfaction Problem (CSP) has a solution is NP-complete. CSPs are solved by inference (i.e., enforcing consistency), conditioning (i.e., doing search), or, more commonly, by interleaving the two mechanisms. The most common consistency property enforced during search is Generalized Arc Consistency (GAC). In recent years, new algorithms that enforce consistency properties stronger than GAC have been proposed and shown to be necessary to solve difficult problem instances.

We frame the question of balancing the cost and the pruning effectiveness of consistency algorithms as the question of determining where, when, and how much of ...


On Path Consistency For Binary Constraint Satisfaction Problems, Christopher G. Reeson Dec 2016

On Path Consistency For Binary Constraint Satisfaction Problems, Christopher G. Reeson

Computer Science and Engineering: Theses, Dissertations, and Student Research

Constraint satisfaction problems (CSPs) provide a flexible and powerful framework for modeling and solving many decision problems of practical importance. Consistency properties and the algorithms for enforcing them on a problem instance are at the heart of Constraint Processing and best distinguish this area from other areas concerned with the same combinatorial problems. In this thesis, we study path consistency (PC) and investigate several algorithms for enforcing it on binary finite CSPs. We also study algorithms for enforcing consistency properties that are related to PC but are stronger or weaker than PC.

We identify and correct errors in the literature ...