Reactive C: An extension of C to program reactive systems

Reactive systems are interactive programs that react continuously to sequences of activations coming from the external world. Reactive programming leads to a new programming style where one programs in terms of reactions to activations and reasons in a logic of instants. This paper describes an extension of the C programming language called RC (for ‘Reactive C’) to program reactive systems. The language RC is described, then some programming examples are given to illustrate the reactive approach. The main RC notions come directly from the Esterel synchronous programming language. Finally, the Esterel and RC languages are compared.     

Discovering rules to design newspapers: An inductive constraint logic programming approach

Inductive logic programming combines both machine learning and logic programming techniques. ILP uses first-order predicate logic restricted to Horn clauses as an underlying language. Thus, programs induced by an ILP system inherit the classical limitations of PROLOG programs. Constraint logic programming avoids some of the limitations of logic programming, and so ILP aims to induce programs that employ this paradigm. Current ILP systems that induce constrained logic programs extend systems based on the normal semantics ofILP. In this article we introduce IC-Log, a new system that induces constrained logic programs and relies on an extension ofa nonmonotonic semantics-based system. We then present an application of IC-Log in the field ofcomputer-aided publishing.     

处理指针相等关系不确定的指针逻辑

为类C小语言PointerC设计的指针逻辑是Hoare逻辑的一种扩展,可用来对指针程序进行精确的指针分析,以支持指针相等关系确定的程序的安全性验证.通过增加相等关系不确定的指针类型访问路径集合,可扩展这种指针逻辑,使得扩展后的指针逻辑可以应用于有向图等指针相等关系不确定的抽象数据结构上的指针程序性质　证明.     

Consistency properties and set based logic programming

Blair et al. (2001) developed an extension of logic programming called set based logic programming. In the theory of set based logic programming the atoms represent subsets of a fixed universe X and one is allowed to compose the one-step consequence operator with a monotonic idempotent operator O so as to ensure that the analogue of stable models in the theory are always closed under O. Marek et al. (1992, Ann Pure Appl Logic 96:231–276 1999) developed a generalization of Reiter’s normal default theories that can be applied to both default theories and logic programs which is based on an underlying consistency property. In this paper, we show how to extend the normal logic programming paradigm of Marek, Nerode, and Remmel to set based logic programming. We also show how one can obtain a new semantics for set based logic programming based on a consistency property.     

一种用于指针程序的形状分析方法

指针程序的分析一直是研究热点。本文提出一种基于形状图逻辑的形状分析方法,其中形状分析采用形状图来表达程序中指针的指向和相等关系,并用形状图逻辑来进行推理。形状图逻辑是一种把形状图看成有关指针的断言,并在此基础上对Hoare逻辑进行扩展而得到的程序逻辑。首先介绍所提出的形状图和形状图逻辑;然后在此基础之上,设计一种基于形状图逻辑的形状分析方法。     

Partial equilibrium logic

Partial equilibrium logic (PEL) is a new nonmonotonic reasoning formalism closely aligned with logic programming under well-founded and partial stable model semantics. In particular it provides a logical foundation for these semantics as well as an extension of the basic syntax of logic programs. In this paper we describe PEL, study some of its logical properties and examine its behaviour on disjunctive and nested logic programs. In addition we consider computational features of PEL and study different approaches to its computation.     

Stable and extension class theory for logic programs and default logics

The stable model semantics (cf. Gelfond and Lifschitz [1]) for logic programs suffers from the problem that programs may not always have stable models. Likewise, default theories suffer from the problem that they do not always have extensions. In such cases, both these formalisms for non-monotonic reasoning have an inadequate semantics. In this paper, we propose a novel idea-that of extension classes for default logics, and of stable classes for logic programs. It is shown that the extension class and stable class semantics extend the extension and stable model semantics respectively. This allows us to reason about inconsistent default theories, and about logic programs with inconsistent completions. Our work extends the results of Marek and Truszczynski [2] relating logic programming and default logics.     

A framework for linguistic logic programming

Lawry's label semantics for modeling and computing with linguistic information in natural language provides a clear interpretation of linguistic expressions and thus a transparent model for real‐world applications. Meanwhile, annotated logic programs (ALPs) and its fuzzy extension AFLPs have been developed as an extension of classical logic programs offering a powerful computational framework for handling uncertain and imprecise data within logic programs. This paper proposes annotated linguistic logic programs (ALLPs) that embed Lawry's label semantics into the ALP/AFLP syntax, providing a linguistic logic programming formalism for development of automated reasoning systems involving soft data as vague and imprecise concepts occurring frequently in natural language. The syntax of ALLPs is introduced, and their declarative semantics is studied. The ALLP SLD‐style proof procedure is then defined and proved to be sound and complete with respect to the declarative semantics of ALLPs. © 2010 Wiley Periodicals, Inc.     

Logic programming with solution preferences

Preference logic programming (PLP) is an extension of logic programming for declaratively specifying problems requiring optimization or comparison and selection among alternative solutions to a query. PLP essentially separates the programming of a problem itself from the criteria specification of its solution selection. In this paper we present a declarative method for specifying preference logic programs. The method introduces a precise formalization for the syntax and semantics of PLP. The syntax of a preference logic program contains two disjoint sets of definite clauses, separating a core program specifying a general computational problem from its preference rules for optimization; the semantics of PLP is given based on the Herbrand model and fixed point theory, where how preferences affects the least Herbrand model of a logic program is interpreted as a sequence of meta-level mapping operations. In addition, we present an operational semantics based on a new resolution strategy and a memoized recursive algorithm for computing strictly stratified logic programs with well-formed preferences, and further show that the operational semantics of such a preference logic program is consistent to its declarative semantics.     

Autoepistemic logic programming

An autoepistemic logic programming language is derived from a subset of a three-valued autoepistemic logic, called 3AEL. Autoepistemic programs generalize several ideas underlying logic programming: stable, supported, and well-founded models, Fitting's semantics, Kunen's semantics, and abductive frameworks can all be captured through simple autoepistemic translations; moreover, SLDNF-resolution and a generate-and-test method for stable semantics are generalized to provide sound and complete proof methods for autoepistemic programs. These methods extend existing proof methods for 3AEL. Thus autoepistemic logic programming, besides contributing to the understanding of 3AEL, can be seen as a unifying framework for the theory of logic programs. It should also be regarded as a first step toward a flexible environment where different forms of inference can be formally integrated.This paper is an extended version of [8]. I am grateful to my advisor, Giorgio Levi, to Paolo Mancarella, who read the first version of the paper, and to the anonymous referees, whose comments led to sensible improvements.     

Strong order equivalence

Recently, strong equivalence for Answer Set Programming has been studied intensively, and was shown to be beneficial for modular programming and automated optimization. In this paper we define the novel notion of strong order equivalence for logic programs with preferences (ordered logic programs). Based on this definition we give, for several semantics for preference handling, necessary and sufficient conditions for programs to be strongly order equivalent. These results allow us also to associate a so-called SOE structure to each ordered logic program, such that two ordered logic programs are strongly order equivalent if and only if their SOE structures coincide. We also present the relationships among the studied semantics with respect to strong order equivalence, which differs considerably from their relationships with respect to preferred answer sets. Furthermore, we study the computational complexity of several reasoning tasks associated to strong order equivalence. Finally, based on the obtained results, we present – for the first time – simplification methods for ordered logic programs.     

Logical approximation for program analysis

The abstract interpretation of programs relates the exact semantics of a programming language to a finite approximation of those semantics. In this article, we describe an approach to abstract interpretation that is based in logic and logic programming. Our approach consists of faithfully representing a transition system within logic and then manipulating this initial specification to create a logical approximation of the original specification. The objective is to derive a logical approximation that can be interpreted as a terminating forward-chaining logic program; this ensures that the approximation is finite and that, furthermore, an appropriate logic programming interpreter can implement the derived approximation. We are particularly interested in the specification of the operational semantics of programming languages in ordered logic, a technique we call substructural operational semantics (SSOS). We show that manifestly sound control flow and alias analyses can be derived as logical approximations of the substructural operational semantics of relevant languages.     

Solving constraint optimization problems from CLP-stylespecifications using heuristic search techniques

Presents a framework for efficiently solving logic formulations of combinatorial optimization problems using heuristic search techniques. In order to integrate cost, lower-bound and upper-bound specifications with conventional logic programming languages, we augment a constraint logic programming (CLP) language with embedded constructs for specifying the cost function and with a few higher-order predicates for specifying the lower and upper bound functions. We illustrate how this simple extension vastly enhances the ease with which optimization problems involving combinations of Min and Max can be specified in the extended language CLP* and we show that CSLDNF (Constraint SLD resolution with Negation as Failure) resolution schemes are not efficient for solving optimization problems specified in this language. Therefore, we describe how any problem specified using CLP* can be converted into an implicit AND/OR graph, and present an algorithm called GenSolve which can branch-and-bound using upper and lower bound estimates, thus exploiting the full pruning power of heuristic search techniques. A technical analysis of GenSolve is provided. We also provide experimental results comparing various control strategies for solving CLP* programs     

Semantics of EqL

The formal semantics of a novel language, called EqL, are presented for first-order functional and Horn logic programming. An EqL program is a set of conditional pattern-directed rules, where the conditions are expressed as a conjunction of equations. The programming paradigm provided by this language may be called equational programming. The declarative semantics of equations is given in terms of their complete set of solutions, and the operational semantics for solving equations is an extension of reduction, called object refinement. The correctness of the operational semantics is established through the soundness and completeness theorems. Examples are given to illustrate the language and its semantics.<>     

A theory of complete logic programs with equality

Incorporating equality into the unification process has added great power to automated theorem provers. We see a similar trend in logic programming where a number of languages are proposed with specialized or extended unification algorithms. There is a need to give a logical basis to these languages. We present here a general framework for logic programming with definite clauses, equality theories, and generalized unification. The classic results for definite clause logic programs are extended in a simple and natural manner. The extension of the soundness and completeness of the negation-as-failure rule for complete logic programs is conceptually more delicate and represents the main result of this paper.     

On the partial semantics for disjunctive deductive databases

Partial stable models for deductive databases, i.e., normal function-free logic programs (also called datalog programs), have two equivalent definitions: one based on 3-valued logics and another based on the notion of unfounded set. The notion of partial stable model has been extended to disjunctive deductive databases using 3-valued logics. In this paper, a characterization of partial stable models for disjunctive datalog programs is given using a suitable extension of the notion of unfounded set. Two interesting sub-classes of partial stable models, M-stable (Maximal-stable) (also called regular models, preferred extension,and maximal stable classes) and L-stable (Least undefined-stable) models, are then extended from normal to disjunctive datalog programs. On the one hand, L-stable models are shown to be the natural relaxation of the notion of total stable model; on the other hand the less strict M-stable models, endowed with a nice modularity property, may be appealing from the programming and computational point of view. M-stable and L-stable models are also compared with the regular models for disjunctive datalog programs recently proposed in the literature.     

Equilibrium logic

Equilibrium logic is a general purpose nonmonotonic reasoning formalism closely aligned with answer set programming (ASP). In particular it provides a logical foundation for ASP as well as an extension of the basic syntax of answer set programs. We present an overview of equilibrium logic and its main properties and uses.Partially supported by CICyT project TIC-2003-9001-C02, URJC project PPR-2003-39 and WASP (IST-2001-37004).     

Iterative belief revision in extended logic programming

Extended logic programming augments conventional logic programming with both default and explicit negation. Several semantics for extended logic programs have been proposed that extend the well-founded semantics for logic programs with default negation (called normal programs). We show that two of these extended semantics are intractable; both Dung's grounded argumentation semantics and the well-founded semantics of Alferes et al. are NP-hard. Nevertheless, we also show that these two semantics have a common core, a more restricted form of the grounded semantics, which is tractable and can be computed iteratively in quadratic time. Moreover, this semantics is a representative of a rich class of tractable semantics based on a notion of iterative belief revision.     

MSVL: a typed language for temporal logic programming

The development of types is an important but challenging issue in temporal logic programming. In this paper, we investigate how to formalize and implement types in the temporal logic programming language MSVL, which is an executable subset of projection temporal logic (PTL). Specifically, we extendMSVL with a few groups of types including basic data types, pointer types and struct types. On each type, we specify the domain of values and define some standard operations in terms of logic functions and predicates. Then, it is feasible to formalize statements of type declaration of program variables and statements of struct definitions as logic formulas. As the implementation of the theory, we extend theMSV toolkit with the support of modeling, simulation and verification of typedMSVL programs. Applications to the construction of AVL tree and ordered list show the practicality of the language.     

双析取逻辑程序设计基础（Ⅰ）

析取逻辑程序设计是传统逻辑程序设计最重要的扩充之一，本文通过一些实例说明，现存语义无法充分 表示信息的不完全性。为此，本文提出了双析取逻辑程序设计的概念，我们不仅从句法上将正规则析取逻辑程序推广为双析取逻辑程序。而且建立了一种高度直观，灵活的辩论语义框架ＢＤＡＳ。