On computability by logic programs

The problem of computational completeness of Horn clause logic programs is revisited. The standard results on representability of all computable predicates by Horn clause logic programs are not related to the real universe on which logic programs operate. SLD-resolution, which is the main mechanism to execute logic programs, may give answer substitutions with variables. As the main result we prove that computability by Horn clause logic programs is equivalent to standard computability over the Herbrand universe with variables. The semantics we use isS-semantics introduced by Falaschi et al. [3]. As an application of the main result we prove the existence of a metainterpreter for a sublanguage of real Prolog, written in the language of Horn clauses with the S-semantics. We also show that the traditional semantics of Prolog do not reflect its computational behavior from the viewpoint of recursion theory.This article is a revised version of [13]. The work was essentially done during author's visit to ECRC.     

Towards a logic programming methodology based on higher-order predicates

This paper outlines a logic programming methodology which applies standardized logic program recursion forms afforded by a system of general purpose recursion schemes. The recursion schemes are conceived of as quasi higher-order predicates which accept predicate arguments, thereby representing parameterized program modules. This use of higher-order predicates is analogous to higher-order functionals in functional programming. However, these quasi higher-order predicates are handled by a metalogic programming technique within ordinary logic programming. Some of the proposed recursion operators are actualizations of mathematical induction principles (e.g. structural induction as generalization of primitive recursion). Others are heuristic schemes for commonly occurring recursive program forms. The intention is to handle all recursions in logic programs through the given repertoire of higher-order predicates. We carry out a pragmatic feasibility study of the proposed recursion operators with respect to the corpus of common textbook logic programs. This pragmatic investigation is accompanied with an analysis of the theoretical expressivity. The main theoretical results concerning computability are

1. Primitive recursive functions can be re-expressed in logic programming by predicates defined solely by non-recursive clauses augmented with afold recursion predicate akin to the fold operators in functional programming.
2. General recursive functions can be re-expressed likewise sincefold allows re-expression of alinrec recursion predicate facilitating linear, unbounded recursion.

     

Deriving protocol specifications from service specifications written in LOTOS

Summary.  A complete communication system is broken down into a number of protocol layers each of which provides services to the layer above it and uses services provided by its underlying layer. A service specification defines a particular ordering of the operations that a given layer provides to the layer above it. The active elements in each layer are called entities and they use a protocol in order to implement their service definition. On the basis of this relation between the service and protocol concepts we have developed algorithms for deriving protocol entity specifications from a formal service specification. The derived protocol entities ensure the correct ordering of the service primitives by exchanging synchronization messages through an underlying communication medium. This paper presents an extended version of our earlier derivation algorithms. This version of the algorithm can handle all operators and unrestricted process invocation and recursion as defined by basis LOTOS. The correctness of this derivation algorithm is formally proved. Received: January 1992 / Accepted: February 1996     

Specification,Verification and Prototyping of an Optimized Compiler

This paper generalizes an algebraic method for the design of a correct compiler to tackle specification and verification of an optimized compiler. The main optimization issues of concern here include the use of existing contents of registers where possible and the identification of common expressions. A register table is introduced in the compiling specification predicates to map each register to an expression whose value is held by it. We define different kinds of predicates to specify compilation of programs, expressions and Boolean tests. A set of theorems relating to these predicates, acting as a correct compiling specification, are presented and an example proof within the refinement algebra of the programming language is given. Based on these theorems, a prototype compiler in Prolog is produced.     

- : an executable specification language for solving all problems in NP

In this paper a logic-based specification language, called - , is presented. The language is obtained by extending through allowing a limited use of some second-order predicates of predefined form. - programs specify solutions to problems in a very abstract and concise way, and are executable. In the present prototype they are compiled to code, which is run to construct outputs. Second-order predicates of suitable form allow to limit the size of search spaces in order to obtain reasonably efficient construction of problem solutions. - expressive power is precisely characterized as to express exactly the problems in the class NP. The specification of several combinatorial problems in - is shown, and the efficiency of the generated programs is evaluated.     

Normalising the associative law: An experiment with Martin-Löf's type theory

Martin-Löf's type theory contains a logic, a specification language and a programming language, so it is a tool with different uses. Although it is traditionally used as anintegrated programming logic, it may well be used as anexternal logic, which is necessary if one wants to use the formalism of type theory to verify the correctness of an external program. Different tools, such as well founded recursion, measure functions, or the separation of correctness into termination and partial correctness, may be used to obtain a correct type theory program. Type theory is viewed as anopen system with respect toinductively defined types and predicates, which makes it easy to represent an external program as agraph. Formal proofs have been edited using Larry Paulson's ISABELLE.     

Resolution approach to testing compatibility of interacting automata

Conclusion The notion of compatibility of automata was proposed in [1] for formalization of requirements that must be met by interacting partial automata. Testing the compatibility of automata is of essential importance for the design of systems that interact with the environment, especially when we use declarative specificatio of the system to be designed. Under the assumptions of this article for the automaton that models the environment, partiality of the specified automaton is a source of possible incompatibility with the environment. When declarative specification is used, we can never decide in advance if the specified automaton is partial or not. Moreover, even a specification thata priori describes a completely defined automaton may be altered by the actions of the designer in the process of design (especially if these actions are incorrect) so that the specified automaton becomes partial. Therefore the initial specification, and each successive specification produced by human intervention in the design process, must be tested for compatibility with the environment. In the methodology of verification design of automata, compatibility testing is used to solve two problems: a) generating the specification of the class of all automata that satisfy the initial specification and are compatible with the specification of the environment; b) testing for correctness the designer's decisions that alter the current specification of the automaton being designed. The results of this article have led to the development of an efficient resolution procedure for testing the compatibility of automaton specification with the specification of the environment. this procedure has been implemented in the system for verification design of automata from their logical specifications. The efficiency of the developed procedure is based on the results of compatibility analysis of automata from [1] and on the restricted resolution strategy whose completeness and correctness have been proved in [2]. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 36–50, November–December, 1994.     

General method of testing the compatibility of interacting automata with finite memory

A method is proposed for compatibility analysis of two interacting partial nondeterministic automata A and B specified in a first-order language with monadic predicates. In contrast to a method proposed earlier, no restrictions are imposed on the form of specification of the automaton B. These investigations were partially supported by INTAS grant 96-0760. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 25–37, November–December, 1999.     

拓广的右线性递归变换算法及其正确性

本文给出拓广的右线性递归变换算法并证明其正确性.拓广的右线性递归中可以包含一个或多个IDB谓词,它是右线性递归的一般化.和右线性递归计算算法一样,本文提供的算法遵循魔集的模式:首先改写规则,然后用半扑质的自底向上算法计算新规则.算法的有效性通过减少递归谓词的元数实现.     

Application of the trace assertion method to the specification,design, and verification of automaton programs

The paper considers the application of the trace assertion method [1] for specification and verification of automaton programs [2–4]. The trace assertion method allows the programmer to define an externally visible behavior of an automaton program in a rigorous way, without considering details of its implementation. The method is employed at the requirements specification stage of the system development. The paper introduces techniques for defining semantics of some elements of an automaton program, especially those involved in interactions with the control system. A formal approach to defining states of automaton programs is described. Results of studies related to the verification of specification requirements for automaton programs are also presented.     

一种测试语言包含的算法

在积自动机基础上,利用互模拟关系引出商自动机,用以解决积自动机的状态组合爆炸问题。进而提出一个自然的测试语言包含的算法,这种算法的空间复杂度与规范自动机的状态目呈指数关系即O（2^k),其中K是规范自动机的状态数目。     

Semantics of under-determined expressions

Some specification languages, such as VDM-SL, allow expressions whose values are not fully determined. This may be convenient in cases where the choice of value should be left to a later stage of development.We consider a simple functional language including such under-determined expressions and present a denotational semantics for the language along with a set of proof rules for reasoning about properties of under-determined expressions. One of the specific problems considered is the combination of under-determinedness and a least fixed point semantics of recursion. Soundness of the proof rules is also discussed.     

HYPERINCURSIVE METHODS FOR GENERATING FRACTALS IN AUTOMATA RELATED TO DIFFUSION AND WAVE EQUATIONS

This paper provides modelling tools for automata design in the field of information and formal systems. The concept and methods of incursion and hyperincursion are firstly applied to the Fractal Machine, a hyperiacursive cellular automaton with sequential computations with exclusive OR, where time plays a central role. Simulations will show the generation of fractal patterns. The computation is incursive, for inclusive recursion, in the sense that an automaton is computed at the future time l+1 as a function of its neighbour automata at the present and/or past time steps but also at the future time l+1. The hyperincursion is an incursion when several values can be generated at each time step. External incursive inputs cannot be transformed to recursion. (This is really an example of the Final Cause of Aristotle.) But internal incursive inputs defined at the future time can be transformed to recursive inputs by self-reference. A particular case of self-reference with the Fractal Machine shows a non deterministic hyper-incursive field. Interference of particles in the Fractal Machine gives rise to fractal patterns which follow Huygens Principle of Secondary Sources. The superimposition of states is similar to Deutsch's quantum computing principle. This is also related to digital cellular automata obtained from diffusion and wave finite difference equations. Zuse proposed to represent physical systems by a computing space based on such a digitalisation of differential equations. I show that the digital wave equation exhibits waves by digital particles with interference effects and uncertainty.     

Simplifying dynamic programming via mode‐directed tabling

In the dynamic programming paradigm the value of an optimal solution is recursively defined in terms of optimal solutions to subproblems. Such dynamic programming definitions can be tricky and error‐prone to specify. This paper presents an elegant method based on tabled logic programming (TLP) that simplifies the specification of such dynamic programming solutions. Our method introduces a new mode declaration for tabled predicates. The arguments of each tabled predicate are divided into indexed and non‐indexed arguments so that tabled predicates can be regarded as functions: indexed arguments represent input values and non‐indexed arguments represent output values. The non‐indexed arguments in a tabled predicate can be further declared to be aggregated, for example, the minimum, so that while generating answers, the global table will dynamically maintain the smallest value for that argument. This mode‐declaration scheme, coupled with recursion, provides an easy‐to‐use method for dynamic programming: there is no need to define the value of an optimal solution recursively, as the definition of a general solution suffices. The optimal value as well as its corresponding concrete solution can be derived implicitly and automatically using tabled logic programming systems. Our experimental results show that mode declarations improve performance in solving dynamic programming problems on TLP systems. Copyright © 2007 John Wiley & Sons, Ltd.     

Ordering Techniques for Two- and Three-Dimensional Convection-Dominated Elliptic Boundary Value Problems

Multigrid methods with simple smoothers have been proven to be very successful for elliptic problems with no or only moderate convection. In the presence of dominant convection or anisotropies as it might appear in equations of computational fluid dynamics (e.g. in the Navier-Stokes equations), the convergence rate typically decreases. This is due to a weakened smoothing property as well as to problems in the coarse grid correction. In order to obtain a multigrid method that is robust for convection-dominated problems, we construct efficient smoothers that obtain their favorable properties through an appropriate ordering of the unknowns. We propose several ordering techniques that work on the graph associated with the (convective part of the) stiffness matrix. The ordering algorithms provide a numbering together with a block structure which can be used for block iterative methods. We provide numerical results for the Stokes equations with a convective term illustrating the improved convergence properties of the multigrid algorithm when applied with an appropriate ordering of the unknowns. Received July 12, 1999; revised October 1, 1999     

A MODIFIED METHOD FOR SUPERVISOR SPECIFICATION AND SYNTHESIS OF A CLASS OF DISCRETE EVENT SYSTEMS

In this paper, a model‐refining method is proposed to alleviate the complexity involved in specification interpretation of DES control problems. The legal constraint language is defined in terms of illegal states and events in contrast with constructing the automaton of the specification language. This method could provide a more intuitive view of the DES control problem and would be suitable for practical implementation. Two examples, which have commonly been used in the literature, are employed to show the efficiency of the proposed method. Further, under this framework, it is shown that the supremal controllable sublanguage can take a simpler form based on the concept of an illegal state set. A state‐based supervisor synthesis procedure is presented, and a simple example is provided.     

A framework for multi-robot motion planning from temporal logic specifications

We propose a framework for the coordination of a network of robots with respect to formal requirement specifications expressed in temporal logics.A regular tessellation is used to partition the space of interest into a union of disjoint regular and equal cells with finite facets,and each cell can only be occupied by a robot or an obstacle.Each robot is assumed to be equipped with a finite collection of continuous-time nonlinear closed-loop dynamics to be operated in.The robot is then modeled as a hybrid automaton for capturing the finitely many modes of operation for either staying within the current cell or reaching an adjacent cell through the corresponding facet.By taking the motion capabilities into account,a bisimilar discrete abstraction of the hybrid automaton can be constructed.Having the two systems bisimilar,all properties that are expressible in temporal logics such as Linear-time Temporal Logic,Computation Tree Logic,and μ -calculus can be preserved.Motion planning can then be performed at a discrete level by considering the parallel composition of discrete abstractions of the robots with a requirement specification given in a suitable temporal logic.The bisimilarity ensures that the discrete planning solutions are executable by the robots.For demonstration purpose,a finite automaton is used as the abstraction and the requirement specification is expressed in Computation Tree Logic.The model checker Cadence SMV is used to generate coordinated verified motion planning solutions.Two autonomous aerial robots are used to demonstrate how the proposed framework may be applied to solve coordinated motion planning problems.     

Absolute controllability of predicates in discrete event systems

The absolute controllability of predicates in discrete event systems is studied in this paper. A predicate is absolutely controllable if it is control-invariant and the states specified by it are mutually reachable via legal states. It is shown that there is a global state feedback such that the resultant closed-loop system is strongly connected if and only if the predicate is absolutely controllable. The weakest absolutely controllable predicate stronger than the given predicate is shown to exist with respect to the given initial state. Based on the notion of the dual automaton a graph-theoretic algorithm is given to compute the set of weakest absolutely controllable predicates stronger than the given predicate. Application of the concept of absolutely controllable predicate to a class of optimal control problem is discussed. Examples are given to illustrate the results     

基于Z规格说明的软件测试用例自动生成

提出了一种基于Ｚ规格说明的软件测试用例自动生成方法,通过对软件Ｚ规格说明的分析,找出描述软件输入、输出约束的线性谓词,经过经性谓词转换,线性谓词到线性不等式组的转换,找出区域边界顶点和边界附近的测试点等过程自动生成测试用例。同时还介绍了基于Ｚ规格说明的软件测试用例自动生成方法的实例,并通过一个实例进一步加以说明。