Translating a Linear Logic Programming Language into Java

There have been several proposals for logic programming language based on linear logic: Lolli [8], Lygon [7], LO [3], LinLog [2], Forum [11], HACL [10]. In these languages, it is possible to create and consume resources dynamically as logical formulas. The efficient handling of resource formulas is, therefore, an important issue in the implementation of these languages. Lolli, Lygon, and Forum are implemented as interpreter systems; Lolli is on SML and λProlog, Lygon is on Prolog, Forum is on SML, λProlog and Prolog. However, none of them have been implemented in Java.In this paper, we describe the Prolog Café ¹ system which translates a linear logic programming language called LLP to Java via the LLPAM [12] [5], an extension of the standard WAM [16] [1] for LLP. LLP is a superset of Prolog and a subset of Lolli. The main difference from the first implementation [4] is resource compilation. That is to say, resource formulas are compiled into closures which consist of a reference of compiled code and a set of bindings for free variables. Calling these resources is integrated with the ordinary predicate invocation.Prolog Café is portable to any platform supporting Java and easily expandable with increasing Java's class libraries. In performance, on average, Prolog Café generate 2.2 times faster code for a set of classical Prolog benchmarks compared with jProlog.     

A Critical Reexamination of Default Logic, Autoepistemic Logic, and Only Knowing

Fifteen years of work on nonmonotonic logic has certainly increased our understanding of the area. However, given a problem in which nonmonotonic reasoning is called for, it is far from clear how one should go about modeling the problem using the various approaches. We explore this issue in the context on two of the best–known approaches, Reiter's default logic and Moore's autoepistemic logic, as well as two related notions of "only knowing," due to Halpern and Moses and to Levesque. In particular, we return to the original technical definitions given in these papers and examine the extent to which they capture the intuitions they were designed to capture.     

Operational Concepts of Nonmonotonic Logics Part 2: Autoepistemic Logic

The subject of nonmonotonic reasoning is reasoning with incompleteinformation. One of the main approaches is autoepistemic logic inwhich reasoning is based on introspection. This paper aims at providing a smooth introduction to this logic,stressing its motivation and basic concepts. The meaning (semantics)of autoepistemic logic is given in terms of so-called expansionswhich are usually defined as solutions of a fixed-point equation. Thepresent paper shows a more understandable, operational method fordetermining expansions. By improving applicability of the basicconcepts to concrete examples, we hope to make a contribution to awider usage of autoepistemic logic in practical applications.     

A Logic Based Asynchronous Multi-Agent System

We present a logic programming based asynchronous multi-agent system in which agents can communicate with one another; update themselves and each other; abduce hypotheses to explain observations, and use them to generate actions. The knowledge base of the agents is comprised of generalized logic programs, integrity constraints, active rules, and of abducibles. We characterize the interaction among agents via an asynchronous transition rule system, and provide a stable models based semantics. An example is developed to illustrate how our approach works.     

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.     

A Resource Logic for Multi-Agent Plan Merging

In a multi-agent system, agents are carrying out certain tasks by executing plans. Consequently, the problem of finding a plan, given a certain goal, has been given a lot of attention in the literature. Instead of concentrating on this problem, the focus of this paper is on cooperation between agents which already have constructed plans for their goals. By cooperating, agents might reduce the number of actions they have to perform in order to fulfill their goals. The key idea is that in carrying out a plan an agent possibly produces side products that can be used as resources by other agents. As a result, an other agent can discard some of its planned actions. This process of exchanging products, called plan merging, results in distributed plans in which agents become dependent on each other, but are able to attain their goals more efficiently. In order to model this kind of cooperation, a new formalism is developed in which side products are modeled explicitly. The formalism is a resource logic based on the notions of resource, skill, goal, and service. Starting with some resources, an agent can perform a number of skills in order to produce other resources which suffice to achieve some given goals. Here, a skill is an elementary production process taking as inputs resources satisfying certain constraints. A service is a serial or parallel composition of skills acting as a program. An operational semantics is developed for these services as programs. Using this formalism, an algorithm for plan merging is developed, which is anytime and runs in polynomial time. Furthermore, a variant of this algorithm is proposed that handles the exchange of resources in a more flexible way. The ideas in the paper will be illustrated by an example from public transportation.     

多Agent合作逻辑中的动作与意图

改进并发博弈结构,给出了一个新模型.消除了不同Agent不准执行相同动作这个与常识不符的假定.给出了5个动作相关函数,使得对Agent、动作与状态三者之间的关系在社会法律约束下的深入考察成为可能.在语法层面同时表述动作和社会法律,提高了多Agent合作逻辑的灵活性和表达能力.在多Agent合作逻辑中引入信念算子和意图算子;考察了两种个体意图和两种群体意图;给出了对命题的个体意图的多子集语义,并把它拓展到对命题的群体意图的语义.     

一各上从源程序代码到其流程图的自动转换算法

本文介绍了一种算法能将源程序代码自动转换成其程序流程图，在软件单元测试阶段，用来检测编码与详细设计的不一致性，从而及时发现并纠正潜在的错误，提高了软件的可靠性，实距表明本算法是有效的。     

多Agent信念逻辑及其在概率意义下的推广

首先建立了一种多Agent信念逻辑MBL(multi-agentbelieflogic),在经典信念逻辑基础上增加了普遍信念算子和公共信念算子,给出MBL的Kripke语义与广义Aumann语义,讨论了两者的等价性,证明了MBL对于上述两种语义的可靠性和完备性.其次,建立了一种多Agent概率信念逻辑MPBL(multi-agentprobabilisticbelieflogic),通过在广义Aumann语义基础上引入概率空间,给出了MPBL的概率Aumann语义,证明了它的可靠性,并给出MPBL的一些推论.     

基于动态描述逻辑的多主体协作模型

基于动态描述逻辑的主体模型和协作过程就是既考虑了智能主体的知识表示与推理问题,又紧密地结合主体的设计与编程问题,把表示与推理应用到主体的具体设计中.它充分利用了动态描述逻辑的统一的形式化框架,同时从静态的知识表示与推理和动态的运行与变化两个方面来刻画主体的心智状态和协作过程,探讨了主体信念、行为能力、目标和规划等心智要素的表示、推理与修改以及联合目标的形成、多目标的规划问题.多主体协作模型将理论和实践有机地结合起来,能够充分体现智能主体的本质特征与运行机制,为多主体系统的设计与编程奠定了很好的基础.     

Compositional Verification of Multi-Agent Systems in Temporal Multi-Epistemic Logic

Compositional verification aims at managing the complexity of theverification process by exploiting compositionality of the systemarchitecture. In this paper we explore the use of a temporal epistemiclogic to formalize the process of verification of compositionalmulti-agent systems. The specification of a system, its properties andtheir proofs are of a compositional nature, and are formalized within acompositional temporal logic: Temporal Multi-Epistemic Logic. It isshown that compositional proofs are valid under certain conditions.Moreover, the possibility of incorporating default persistence ofinformation in a system, is explored. A completion operation on aspecific type of temporal theories, temporal completion, is introducedto be able to use classical proof techniques in verification withrespect to non-classical semantics covering default persistence.     

A Program Logic for Bytecode

Program logics for bytecode languages such as Java bytecode or the .NET CIL can be used to apply Proof-Carrying Code concepts to bytecode programs and to verify correctness properties of bytecode programs. This paper presents a Hoare-style logic for a sequential bytecode kernel language similar to Java bytecode and CIL. The logic handles object-oriented features such as inheritance, dynamic method binding, and object structures with destructive updates, as well as unstructured control flow with jumps. It is sound and complete.     

时态逻辑与程序验证

近年来,时态逻辑大量应用于程序验证,采取的途径随使用的时态逻辑的形式和方法的不同而异。本文用自动机理论研究几种时态逻辑(LTL,BTL,POTL)的模型和模型生成子,并讨论用时态逻辑进行程序验证的的重要途径。     

Translating VDM specifications into ABC programs

Declarative languages such as Miranda and Prolog have often been used to prototype specifications written in the formal notation of VDM, but they have no destructive assignment commands thus making it difficult to model VDM state changes. Imperative languages like C and Pascal allow state changes to be modelled naturally but lack the expressive power to make prototyping feasible. ABC, on the other hand, is a simple yet very powerful imperative language that has a great expressive power making it suitable as a prototyping language. This paper describes the process of translating VDM specifications into ABC programs.     

Translating a knowledge base into HTML

The problem treated in this paper is the slow response of inference engines, especially in a multi-user environment. In this paper, we present a solution that caches all the possible answers to all the possible consultations, by means of translating the entire knowledge base into a set of HTML documents. We prove that the consumption of memory in this case is acceptable (depends linearly on the number of rules in the initial knowledge base), and that the translational algorithm has polynomial complexity. This solution outperforms any other possible solution, since in this case the infering time becomes equal to zero.     

Translating Mobile Ambients into P Systems

We present a translation of the mobile ambients without communication and replication into P systems with mobile membranes. We introduce a set of developmental rules over membranes, and describe the correspondence between the behaviour of an ambient and the evolution of its translated membrane system. We give an operational correspondence result between the mobile ambients and P systems.     

Translating Double Dispatch into Single Dispatch

Goals of flexibility and re-usability in typed object-oriented languages suggest the requirement of double dispatch, i.e., the mechanism of dynamically selecting a method not only according to the run-time type of the receiver (single dispatch), but also to the run-time type of the argument. However, many mainstream languages, such as, e.g., C++ and Java, do not provide it, resorting to only single dispatch. In this paper we present a general technique for adding double dispatch as a type-safe language feature, so yielding dynamic overloading and covariant specialization of methods, without extending basic semantics. To this aim we introduce a toy core language, extended to a full form of (non encapsulated) multi methods. Then we define a translation algorithm from multi methods to the core language, that implements double dispatch by using only standard mechanisms of static overloading and single dispatch. As a main feature, our translation preserves type safety, it uses neither RTTI nor type downcasts and does not introduce crucial overhead during method selection.     

Translating Iterative Algorithms into Automaton Ones

It is shown that the scheme of any iterative algorithm (program) can be realized by a do-while statement with a switch statement as its body that realizes the finite-state automaton transition graph constructed formally by the given scheme. This realization is simpler than that by the Ashcroft–Manna method.