Thesis (Ph.D.) - University of St Andrews, September 2007.

Thesis (M.S.)--University of Missouri-Columbia, 2005. / The entire dissertation/thesis text is included in the research.pdf file; the official abstract appears in the short.pdf file (which also appears in the research.pdf); a non-technical general description, or public abstract, appears in the public.pdf file. Title from title screen of research.pdf file viewed on (December 12, 2006) Includes bibliographical references.

Variable symmetries in constraint satisfaction problems can be broken by adding lexicographic ordering constraints. Existing general methods of generating such sets of ordering constraints can produce a huge number of additional constraints. This adds an unacceptable overhead to the solving process. Methods exist by which this large set of constraints can be reduced to a much smaller set automatically, but their application is also prohibitively costly. In contrast, this thesis takes a bottom up approach to generating symmetry breaking constraints. This will involve examining some commonly-occurring families of mathematical groups and deriving a general formula to produce a minimal set of ordering constraints which are sufficient to break all of the symmetry that each group describes. In some cases it is known that there exists no manageable sized sets of constraints to break all symmetries. One example of this occurs with matrix row and column symmetries. In such cases, incomplete symmetry breaking has been used to great effect. Double lex is a commonly used incomplete symmetry breaking technique for row and column symmetries. This thesis also describes another similar method which compares favourably to double lex. The general formulae investigated are used as building blocks to generate small sets of ordering constraints for more complex groups, constructed by combining smaller groups. Through the utilisation of graph automorphism tools and the groups and permutations software GAP we provide a method of defining variable symmetries in a problem as a group. Where this group can be described as the product of smaller groups, with known general formulae, we can construct a minimal set of ordering constraints for that problem automatically. In summary, this thesis provides the theoretical background necessary to apply efficient static symmetry breaking to constraint satisfaction problems. It also goes further, describing how this process can be automated to remove the necessity of having an expert CP practitioner, thus opening the field to a larger number of potential users.

Thesis (Ph. D.)--University of Kentucky, 2001. / Title from document title page. Document formatted into pages; contains vii, 75 p. : ill. Includes abstract. Includes bibliographical references (p. 70-72).

Monitoring of user-defined constraints on time-varying data is a fundamental functionality in various sensor-based real-time applications such as environmental monitoring, process control, location-based surveillance, etc. In general, these applications track real-world objects and constantly evaluate the constraints over the object trace to take a timely reaction upon their violation or satisfaction. While it is ideal that all the constraints are evaluated accurately in real-time, data streams often contain incomplete and delayed information, rendering the evaluation results of the constraints uncertain to some degree. In this dissertation, we provide a comprehensive approach to the problem of monitoring constraint-based queries over data streams for which the data or timestamp values are inherently uncertain. First, we propose a generic framework, namely Ptmon, for monitoring timing constraints and detecting their violation early, based on the notion of probabilistic violation time. In doing so, we provide a systemic approach for deriving a set of necessary timing constraints at compilation time. Our work is innovative in that the framework is formulated to be modular with respect to the probability distributions on timestamp values. We demonstrate the applicability of the framework for different timestamp models. Second, we present a probabilistic timing join operator, namely Ptjoin, as an extended functionality of Ptmon, which performs stream join operations based on temporal proximity as well as temporal uncertainty. To efficiently check the Ptjoin condition upon event arrivals, we introduce the stream-partitioning technique that delimits the probing range tightly. Third, we address the problem of monitoring value-based constraints that are in the form of range predicates on uncertain data values with confidence thresholds. A new monitoring scheme Spmon that can reduce the amount of data transmission and thus expedite the processing of uncertain data streams is introduced. The similarity concept that was originally intended for real-time databases is extended for our probabilistic data stream model where each data value is given by a probability distribution. In particular, for uniform and gaussian distributions, we show how we derive a set of constraints on distribution parameters as a metric of similarity distances, exploiting the semantics of probabilistic queries being monitored. The derived constraints enable us to formulate the probabilistic similarity region that suppresses unnecessary data transmission in a monitoring system. / text

Constraint satisfaction problems (CSPs) provide a unified framework for studying a wide variety of computational problems naturally arising in combinatorics, artificial intelligence and database theory. To any finite domain D and any constraint language Γ (a finite set of relations over D), we associate the constraint satisfaction problem CSP(Γ): an instance of CSP(Γ) consists of a list of variables x1, x2,..., x n and a list of constraints of the form "(x 7, x2,..., x5) ∈ R" for some relation R in Γ. The goal is to determine whether the variables can be assigned values in D such that all constraints are simultaneously satisfied. The computational complexity of CSP(Γ) is entirely determined by the structure of the constraint language Γ and, thus, one wishes to identify classes of Γ such that CSP(Γ) belongs to a particular complexity class. / In recent years, logical and algebraic perspectives have been particularly successful in classifying CSPs. A major weapon in the arsenal of the logical perspective is the database-theory-inspired logic programming language called Datalog. A Datalog program can be used to solve a restricted class of CSPs by either accepting or rejecting a (suitably encoded) set of input constraints. Inspired by Dalmau's work on linear Datalog and Reingold's breakthrough that undirected graph connectivity is in logarithmic space, we use a new restriction of Datalog called symmetric Datalog to identify a class of CSPs solvable in logarithmic space. We establish that expressibility in symmetric Datalog is equivalent to expressibility in a specific restriction of second order logic called Symmetric Restricted Krom Monotone SNP that has already received attention for its close relationship with logarithmic space. / We also give a combinatorial description of a large class of CSPs lying in L by showing that they are definable in symmetric Datalog. The main result of this thesis is that directed st-connectivity and a closely related CSP cannot be defined in symmetric Datalog. Because undirected st-connectivity can be defined in symmetric Datalog, this result also sheds new light on the computational differences between the undirected and directed st-connectivity problems.

Thesis (Ph. D.)--University of Texas at Austin, 2008. / Vita. Includes bibliographical references.

Thesis (M.S. in Computer Science)--Naval Postgraduate School, Sept. 2004. / Thesis advisor(s): George W. Dinolt. Includes bibliographical references (p. 133-136). Also available online.

Thesis (Ph. D.)--University of Washington, 2000. / Vita. Includes bibliographical references (p. 154-165).

No description available.