Digitized by Kansas Correctional Industries

No description available.

A new declarative language is presented which captures the expressibility of both logic programming languages and functional languages. This is achieved by conditional graph rewriting, with full unification as the parameter passing mechanism. The syntax and semantics are described both formally and informally, and examples are offered to support the expressibility claim made above. The language design is of further interest due to its uniformity and the inclusion of a novel mechanism for type inference in the presence of derived type hierarchies

A programming language that combines the best aspects of both the functional and logic paradigms with a complete evaluation strategy has been a goal of a Portland State University project team for the last several years. I present the third in a series of modifications to the compiler of the logic programming language Goedel which reaches this goal. This enhancement of Goedel's compiler translates user-defined functions in the form of rewrite rules into code that performs evaluation of these functions by the strategy of needed narrowing. In addition, Goedel's mechanism that evaluates predicates is supplemented so that needed narrowing is still maintained as the evaluation strategy when predicates possess functional arguments.

Not available / 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, 2005. / Supervisor: Vladimir Lifschitz. Vita. Includes bibliographical references.

No description available.

Answer set programming (ASP) is a form of declarative programming oriented towards difficult combinatorial search problems. It has been applied, for instance, to plan generation and product configuration problems in artificial intelligence and to graph-theoretic problems arising in VLSI design and in historical linguistics. Syntactically, ASP programs look like Prolog programs, but the computational mechanisms used in ASP are different: they are based on the ideas that have led to the development of fast satisfiability solvers for propositional logic. ASP is based on the answer set/stable model semantics for logic problems, originally intended as a specification for query answering in Prolog. From the original definition of 1988, the semantics was independently extended by different research groups to more expressive kinds of programs, with syntax and semantics that are incompatible with each other. In this thesis we study how the various extensions are related to each other. In order to do that, we propose another definition of an answer set. This definition has three main characteristics: (i) it is very simple, (ii) its syntax is more general than the usual concept of a logic program, and (iii) strong theoretical tools can be used to reason on it. About (ii), we show that our syntax allows constructs defined in many other extensions of the answer sets semantics. This fact, together with (iii), allows us to study the expressiveness of those constructs. We also compare the answer set semantics with another important formalism developed by Norm McCain and Hudson Turner, called logic. / text

The general area of developing, applying and studying new and parallel models of computation is motivated by a need to overcome the limits of current Von Neumann based architectures. A key area of research in understanding how new technology can be applied to Al problem solving is through using logic languages. Logic programming languages provide a procedural interpretation for sentences of first order logic, mainly using a class of sentence called Horn clauses. Horn clauses are open to a wide variety of parallel evaluation models, giving possible speed-ups and alternative parallel models of execution. The research in this thesis is concerned with investigating one class of parallel logic language known as Committed Choice Non-Deterministic languages. The investigation considers the inherent parallel behaviour of Al programs implemented in the CCND languages and the effect of various alternatives open to language implementors and designers. This is achieved by considering how various Al programming techniques map to alternative language designs and the behaviour of these Al programs on alternative implementations of these languages. The aim of this work is to investigate how Al programming techniques are affected (qualitatively and quantitatively) by particular language features. The qualitative evaluation is a consideration of how Al programs can be mapped to the various CCND languages. The applications considered are general search algorithms (which focuses on the committed choice nature of the languages); chart parsing (which focuses on the differences between safe and unsafe languages); and meta-level inference (which focuses on the difference between deep and flat languages). The quantitative evaluation considers the inherent parallel behaviour of the resulting programs and the effect of possible implementation alternatives on this inherent behaviour. To carry out this quantitative evaluation we have implemented a system which improves on the current interpreter based evaluation systems. The new system has an improved model of execution and allows several