Many real problems can be treated as constraint satisfaction problems (CSPs), a type of problem for which efficient tools have been developed. Computing the maximum timing separations between the events of a timing sp...
详细信息
Many real problems can be treated as constraint satisfaction problems (CSPs), a type of problem for which efficient tools have been developed. Computing the maximum timing separations between the events of a timing specification falls into this category. In particular, CLP (BNR) is a constraint logicprogramming language which seems well suited to the problem, allowing to draw from the advantages of both CSPs and logicprogramming. Consistency techniques used for solving general CSPs usually produce approximate answers (partial consistency). However, for some specific timing specifications, that is, systems of strictly linear constraints, systems of either max-only or min-only constraints, and systems where linear and either max or min constraints intermix, we show that global consistency can be achieved using CLP based on Relational Interval Arithmetic.
We consider disjunctive Datalog, a powerful database query language based on disjunctive gic programming. Briefly, disjunctive Datalog is a variant of Datalog where disjunctions may appear in the rule heads;advanced v...
详细信息
We consider disjunctive Datalog, a powerful database query language based on disjunctive gic programming. Briefly, disjunctive Datalog is a variant of Datalog where disjunctions may appear in the rule heads;advanced versions also allow for negation in the bodies, which can be handled according to a semantics for negation in disjunctive logicprogramming. In particular, we investigate three different semantics for disjunctive Datalog: the minimal model semantics, the perfect model semantics, and the stable model semantics. For each of these semantics, the expressive power and complexity are studied. We show that the possibility variants of these semantics express the same set of queries. In fact, they precisely capture the complexity class Sigma(2)(p). Thus, unless the Polynomial Hierarchy collapses, disjunctive Datalog is more expressive than normal logicprogramming with negation. These results are not only of theoretical interest;we demonstrate that problems relevant in practice such as computing the optimal tour value in the Traveling Salesman Problem and eigenvector computations can be handled in disjunctive Datalog, but not Datalog with negation (unless the Polynomial Hierarchy collapses). In addition, we study modularity properties of disjunctive Datalog and investigate syntactic restrictions of the formalisms.
A system with multiple interacting agents (whether artificial or human) is often best analyzed using game-theoretic tools. Unfortunately, while the formal foundations are well-established, standard computational techn...
详细信息
A system with multiple interacting agents (whether artificial or human) is often best analyzed using game-theoretic tools. Unfortunately, while the formal foundations are well-established, standard computational techniques for game-theoretic reasoning are inadequate for dealing with realistic games, This paper describes the Gala system, an implemented system that allows the specification and efficient solution of large imperfect information games. The system contains the first implementation of a recent algorithm, due to Koller, Megiddo and von Stengel. Experimental results from the system demonstrate that the algorithm is exponentially faster than the standard algorithm in practice, not just in theory. It therefore allows the solution of games that are orders of magnitude larger than were previously possible. The system also provides a new declarative language for compactly and naturally representing games by their rules. As a whole, the Gala system provides the capability for automated game-theoretic analysis of complex real-world situations. (C) 1997 Elsevier Science B.V.
Type theory is one of the most important tools in the design of higher-level programming languages, such as ML. This book introduces and teaches its techniques by focusing on one particularly neat system and studying ...
详细信息
ISBN:
(数字)9780511834738
ISBN:
(纸本)9780521054225
Type theory is one of the most important tools in the design of higher-level programming languages, such as ML. This book introduces and teaches its techniques by focusing on one particularly neat system and studying it in detail. In this way, all the key ideas are covered without getting involved in the complications of more advanced systems, but concentrating rather on the principles that make the theory work in practice. This book takes a type-assignment approach to type theory, and the system considered is the simplest polymorphic one. The author covers all the basic ideas, including the system's relation to propositional logic, and gives a careful treatment of the type-checking algorithm which lies at the heart of every such system. Also featured are two other interesting algorithms that have been buried in inaccessible technical literature. The mathematical presentation is rigorous but clear, making the book at a level which can be used as an introduction to type theory for computer scientists.
The objective of control generation in logicprogramming is to automatically derive a computation rule for a program that is efficient and yet does not compromise program correctness. Progress in solving this importan...
详细信息
We propose a formal framework for functional logicprogramming, supporting lazy functions, non-determinism and polymorphic datatypes whose data constructors obey a given set C of equational axioms. On top of a given C...
详细信息
The subject of control system design is often presented from two different approaches: general principles based on mathematically or experimentally derived theory and case study descriptions of specific realizations i...
详细信息
The subject of control system design is often presented from two different approaches: general principles based on mathematically or experimentally derived theory and case study descriptions of specific realizations in practice. A gap exists between them. Principles or generalizations derived from analysis of case studies are omitted. A good case in point is organization of PLC programs in machine control applications. Examples of typical program order have been scarcely reported in literature, yet these applications are good candidates, because of typical mechanical configurations and functions shared among machines. PLCs were originally developed as a replacement for relay control systems and were programmed as an emulation of a relay panel. Over a period of time, both the availability of hardware and software programming tools as well as increased sophistication of users resulted in a change of PLC programming style away from the relay panel paradigm. It now approximated more closely that of a general purpose computer. This development makes an even stronger case for use of a standard program order in programming PLCs. An outline for a standard PLC program order is presented and possible variations along with trade-offs are discussed. The usefulness of such a standard program order is explored for all stages of software development and usage with particular emphasis on features needed to develop soft-ware on fast-track or concurrent engineering basis.
Many search algorithms have been introduced without correctness proofs, or proved only with respect to an informal semantics of the algorithm. We address this problem by taking advantage of the correspondence between ...
详细信息
This paper illustrates a prototype system, called GPRS, supporting the Generalized Production Rules (GPR) data-base language. The GPR language integrates, in a unified framework, active rules, which allow the specific...
详细信息
This paper illustrates a prototype system, called GPRS, supporting the Generalized Production Rules (GPR) data-base language. The GPR language integrates, in a unified framework, active rules, which allow the specification of event driven computations on data, and deductive rules, which can be used to derive intensional relations in the style of logicprogramming. The prototype realizes the operational semantics of GPR using a unique rule-evaluation engine. The data model of reference is object based and the system is implemented on top of an object oriented DBMS. Hence, the GPRS prototype represents a concrete proposal of an advanced DBMS for complex objects that provides both active and deductive styles of rule programming.
Summary form only given. At Texas Tech University, C S 3461 (Concepts of programming Languages) is a study of programming language theory and design, with Ada 95 as the primary language used. This course is also part ...
详细信息
Summary form only given. At Texas Tech University, C S 3461 (Concepts of programming Languages) is a study of programming language theory and design, with Ada 95 as the primary language used. This course is also part of an eight-course software engineering-related sequence in the Texas Tech undergraduate curriculum. A class in programming language theory and design is of course not primarily concerned with software engineering; however, as the need for languages which support the software engineering methodology has increased, therefore, there has become a need to discuss related issues in the programming languages course, such as object-oriented design, program validation, and proofs of correctness. In addition, as the software engineering content of the introductory programming sequence (which is a prerequisite to this course) has increased, the degree of design and testing required for the programming assignments in this course has also occurred. In 1995, the Department of Computer Science received a grant from the Defense Information Systems Agency' to revise this course so that it primarily revolved around Ada 95 as the language by which design issues are discussed. Besides the class lectures, this four-semester hour course contains a laboratory component which covers Ada 95, Smalltalk, and Prolog. The students learn the languages through the use of laboratory tutorials, and are required to implement programming languages using this knowledge. In this manner, a mixture of theory and practice is provided to the student.
暂无评论