A rewriting logic framework for operational semantics of membrane systems

Existing results in membrane computing refer mainly to P systems’ characterization of Turing computability, also to some polynomial solutions to NP-complete problems by using an exponential workspace created in a “biological way”. In this paper we define an operational semantics of a basic class of P systems, and give two implementations of the operational semantics using rewriting logic. We present some results regarding these implementations, including two operational correspondence results, and discuss why these implementations are relevant in order to take advantage of good features of both structural operational semantics and rewriting logic.     

The Rewriting Logic Semantics Project

Rewriting logic is a flexible and expressive logical framework that unifies denotational semantics and SOS in a novel way, avoiding their respective limitations and allowing very succinct semantic definitions. The fact that a rewrite theory's axioms include both equations and rewrite rules provides a very useful “abstraction knob” to find the right balance between abstraction and observability in semantic definitions. Such semantic definitions are directly executable as interpreters in a rewriting logic language such as Maude, whose generic formal tools can be used to endow those interpreters with powerful program analysis capabilities.     

The semantics of the combination of atomized statements and parallel choice

In this paper we define a uniform language that is an extension of the language underlying the process algebraPA. One of the main extensions of this language overPA is given by so-called atomizing brackets. If we place these brackets around a statement then we treat this statement as an atomic action. Put differently, these brackets remove all interleaving points. We present a transition system for the language and derive its operational semantics. We show that there are several options for defining a transition system such that the resulting operational semantics is a conservative extension of the semantics forPA. We define a semantic domain and a denotational model for the language. Next we define a closure operator on the semantic domain and show how to use this closure operator to derive a fully abstract denotational semantics. Then the algebraic theory of the language is considered. We define a collection of axioms and a term rewrite system based on these axioms. Using this term rewrite system we are able to identify normal forms for the language. It is shown that these axioms capture the denotational equality. It follows that if two terms are provably equal then they have the same operational semantics. Finally, we show how to extend the axiomatization in order to axiomatize its operational equivalence.     

Synchronous set relations in rewriting logic

This paper presents a mathematical foundation and a rewriting logic infrastructure for the execution and property verification of synchronous set relations. The mathematical foundation is given in the language of abstract set relations. The infrastructure, which is written in the Maude system, enables the synchronous execution of a set relation provided by the user. By using the infrastructure, algorithm verification techniques such as reachability analysis and model checking, already available in Maude for traditional asynchronous rewriting, are automatically available to synchronous set rewriting. In this way, set-based synchronous languages and systems such as those built from agents, components, or objects can be naturally specified and simulated, and are also amenable to formal verification in the Maude system. The use of the infrastructure and some of its Maude-based verification capabilities are illustrated with an executable operational semantics of the Plan Execution Interchange Language (PLEXIL), a synchronous language developed by NASA to support autonomous spacecraft operations.     

The formal definition of semantics by string automata

An abstract machine called a string automaton (SA) is introduced in this paper. SAs are motivated by the need to formally define the semantics of programming languages in a manner accessible to the users of the language. The SA notation can be used to represent functions and computations in a clear, concise, graphical, and natural manner. After the class of SAs has been formally defined, it is shown how logic modules (resembling hardware circuit elements) and function modules (which define functions) can be expressed by SAs. Networks of SAs and their application to the construction of parsers is discussed. The definition of the language and hardware components of an interactive programming system by means of SAs is outlined.     

LARS: A learning algorithm for rewriting systems

Whereas there is a number of methods and algorithms to learn regular languages, moving up the Chomsky hierarchy is proving to be a challenging task. Indeed, several theoretical barriers make the class of context-free languages hard to learn. To tackle these barriers, we choose to change the way we represent these languages. Among the formalisms that allow the definition of classes of languages, the one of string-rewriting systems (SRS) has outstanding properties. We introduce a new type of SRS’s, called Delimited SRS (DSRS), that are expressive enough to define, in a uniform way, a noteworthy and non trivial class of languages that contains all the regular languages, , , the parenthesis languages of Dyck, the language of Lukasiewicz, and many others. Moreover, DSRS’s constitute an efficient (often linear) parsing device for strings, and are thus promising candidates in forthcoming applications of grammatical inference. In this paper, we pioneer the problem of their learnability. We propose a novel and sound algorithm (called LARS) which identifies a large subclass of them in polynomial time (but not data). We illustrate the execution of our algorithm through several examples, discuss the position of the class in the Chomsky hierarchy and finally raise some open questions and research directions. This work was supported in part by the IST Program of the European Community, under the PASCAL Network of Excellence, IST-2002-506778. This publication only reflects the authors’ views. Editor: Georgios Paliouras and Yasubumi Sakakibara     

Effective incorporation of function into logic

During the last decade, the integration of functional and logic languages has received widespread attraction for the purpose of offering two different programming styles in one system simultaneously. The main goal is to incorporate the characteristics of the two paradigms coherently, without degrading the performance of the whole system. However, few languages have achieved this goal. Some of them, even though they have a rich set of functions, perform poorly. Others are efficient, but lose some important facilities. The paper proposes a functional logic language Lazy Aflog and its abstract machine FWAM-II as an expressive and efficient mechanism for this incorporation. Lazy Aflog is an extension of logic language in which functions are reduced in the extended unification, called E-unification with lazy evaluation. This extended unification allows Lazy Aflog to process infinite data structures and higher-order functions naturally. FWAM-II is an extension of the Warren Abstract Machine (WAM) in which the instructions and run-time structures to provide the suspension/reactivation of functional closure are added. These facilities enable FWAM-II to support not only resolution but also infinite data structures and higher-order functions efficiently. In addition, the experimental results show that Lazy Aflog and FWAM-II could be a good compromise between expressiveness and efficiency of the integration.     

Uniqueness logic

A uniqueness type system is used to distinguish values which are referenced at most once from values which may be referenced an arbitrary number of times in a program. Uniqueness type systems are used in the Clean and Mercury programming languages to provide efficiently updatable data-structures and I/O without compromising referential transparency.     

Simple restriction in context-free rewriting

Many rewriting systems with context-free productions and with controlled derivations have been studied. On one hand, these systems preserve the simplicity of applications of context-free productions and, on the other hand, they increase the generative power to cover more aspects of natural and programming languages. However, with λ-productions, many of these systems are computationally complete. It gives rise to a natural question of what are the simplest restrictions of the derivation process of context-free grammars to obtain the universal power. In this paper, we present such a simple restriction introducing so-called restricted context-free rewriting systems. These systems are context-free grammars with a function assigning a nonterminal coupled with + or − to each nonterminal. A production is applicable if it is applicable as a context-free production and if the symbol assigned to the left-hand side of the production is coupled with +, then this symbol has to appear in the sentential form, while if coupled with −, it must not appear in the sentential form. This restriction is simpler than most of the other restrictions, since the context conditions are assigned to nonterminals, not to productions, and their type is the simplest possible – a nonterminal.     

Strong equivalence of logic programs under the infinite-valued semantics

We consider the notion of strong equivalence [V. Lifschitz, D. Pearce, A. Valverde, Strongly equivalent logic programs, ACM Transactions on Computational Logic 2 (4) (2001) 526-541] of normal propositional logic programs under the infinite-valued semantics [P. Rondogiannis, W.W. Wadge, Minimum model semantics for logic programs with negation-as-failure, ACM Transactions on Computational Logic 6 (2) (2005) 441-467] (which is a purely model-theoretic semantics that is compatible with the well-founded one). We demonstrate that two such programs are strongly equivalent under the infinite-valued semantics if and only if they are logically equivalent in the corresponding infinite-valued logic. In particular, we show that strong equivalence of normal propositional logic programs is decidable, and more specifically coNP-complete. Our results have a direct implication for the well-founded semantics since, as we demonstrate, if two programs are strongly equivalent under the infinite-valued semantics, then they are also strongly equivalent under the well-founded semantics.     

Multiple robot programming using a concurrent logic language

Advances in robotics has led to the cooperation of multiple robots among themselves and with their industrial automation environment. Efficient interaction with industrial robots thus becomes one of the key factors in the successful utilization of this modern equipment. When multiple manipulators have to be coordinated, there is a need for a new programming approach that facilitates and encompasses the needs of concurrency, synchronization, timing, and communication. Most robot languages have been developed with little attention being given to the integration of the robot with its environment. Currently, there is a gap between the robot capabilities, the task definition environment, and language facilities supplied to use robots.This paper analyzes the needs and then establishes that a concurrent logic programming approach is a step towards achieving a multi-robot knowledgeable task programming. In particular, the FCP dialect of concurrent Prolog is demonstrated, and analyzed.This research is partially supported by the Paul Ivanier Center for research in robots and production management.     

The strong semantics for logic programs

Recently, the well-founded semantics of a logic programP has been strengthened to the well-founded semantics-by-case (WF_C) and this in turn has been strengthened to the extended well-founded semantics (WF_E). Both WF_C(P) and WF_E(P) have thelogical consequence property, namely, if an atomAj is true in the theory Th(P), thenAj is true in the semantics as well. However, neither WF_C nor WF_E has the GCWA property, i.e., if an atomAj is false in all minimal models ofP,Aj may not be false in WF_C(P) (resp. WF_E(P)). We extend the ideas in WF_C and WF_E to define a strong well-founded semantics WF_S which has the GCWA property. The strong semantics WF_S(P) is defined by combining GCWA with the notion ofderived rules. Here we use a new Type-III derived rules in addition to those used in WF_C and WF_E. The relationship between WF_S and WF_C is also clarified.     

Recursive parser optimization by rewriting context-free grammars

The analysis of programming languages is a fundamental activity in the process of comprehending, maintaining, documenting and reengineering old software. However, the analysis may sometimes be inefficient because of the parsing methodology adopted. Prolog parsers, for instance, have two main drawbacks: the time spent on extracting information as a result of the backtracking mechanism, and the large memory occupation involved. This paper presents an algorithm that optimizes a top-down parser by imposing a set of rules on the grammar to be analyzed. A methodology is then defined for rewritting a context-free grammar (LL(n) n > = 1), and a tool that can achieve this is illustrated. This tool, called FACTOTUM, has been implemented in LPA Prolog, and works on a PC (IBM-MSDOS) through the Windows medium. FACTOTUM is composed of nearly 250 productions, and is an important part of another reverse engineering tool called RE_Tool (Giannone and Maresca, 1995) which can analyze codes in a multilanguage environment. RE_Tool has been implemented in the software engineering laboratories of DIS at the University of Naples Federico II, where it is currently under experimentation.     

An implementation of syntax directed functional programming on nested-stack machines

This paper contributes to the field of functional programming languages. We investigate the call-by-name and call-by-need implementation of a restricted type of functional programming, calledsyntax directed functional programming; the target of this implementation is an abstract machine that is based on nested stacks. In fact, the technical kernel of this paper is a refinement of an automata theoretical result that, roughly speaking, investigates the well-known relationship recursion = iteration + stack in the framework of tree transducers. More precisely, in the underlying result the class of functions computed by total deterministic macro tree-to-string transducers with the call-by-name computation strategy is characterized by total deterministic checking-tree nested-stack transducers. Note that total deterministic macro tree-to-string transducers are term rewriting systems by means of which the reduction semantics of syntax directed functional programming languages can be described.The work of this author has been supported by the Deutsche Forschungsgemeinschaft (DFG).     

A metalogic programming approach: language,semantics and applications

Abstract

This paper presents a logic programming language of novel conception, called Reflective Prolog, which allows declarative metaknowledge representation and metareasoning. The language is defined by augmenting pure Prolog (Horn clauses) with capabilities of self-reference and logical reflection. Self-reference is designed as a quotation device (a carefully defined naming relation) which allows the construction of metalevel terms that refer to object-level terms and atoms. Logical reflection is designed as an unquotation mechanism (a distinguished truth predicate) which relates names to what is named, thus extending the meaning of domain predicates. The reflection mechanism is embodied in an extended resolution procedure which automatically switches the context between levels. This implicit reflection relieves the programmer from having to explicitly deal with control aspects of the inference process. The declarative semantics of a Reflective Prolog definite program P is provided in terms of the least reflective Herbrand model of P, characterized by means of a suitable mapping defined over the Herbrand interpretations of P. The extended resolution is proved sound and complete with respect to the least reflective Herbrand model. By illustrating Reflective Prolog solutions to an organic set of problems, and by discussing the main differences with respect to other approaches to logic metaprogramming, we show that the proposed language deploys, within its field of action, greater expressive and inferential power than those available till now. The interpreter of the language has been fully implemented. Because of its enhanced power, logic semantics and working interpreter, Reflective Prolog is offered as a contribution toward making the declarative approach of logic programming applicable to the development of increasingly sophisticated knowledge-based systems.     

RFuzzy: Syntax, semantics and implementation details of a simple and expressive fuzzy tool over Prolog

We present the RFuzzy framework, a Prolog-based tool for representing and reasoning with fuzzy information. The advantages of our framework in comparison to previous tools along this line of research are its easy, user-friendly syntax, and its expressivity through the availability of default values and types.In this approach we describe the formal syntax, the operational semantics and the declarative semantics of RFuzzy (based on a lattice). A least model semantics, a least fixpoint semantics and an operational semantics are introduced and their equivalence is proven. We provide a real implementation that is free and available. (It can be downloaded from http://babel.ls.fi.upm.es/software/rfuzzy/.) Besides implementation details, we also discuss some actual applications using RFuzzy.     

Modeling multi-rate DSP specification semantics for formal transformational design in HOL

The CATHEDRAL Silicon Compilers synthesize hardware for DSP algorithms specified in Silage, a high level applicative language. In order to optimize the results of the silicon compilation in terms of chip-area and/or throughput, the user often massages the specification applying transformations to the Silage code. To guarantee that the transformations preserve the behavior of the specified algorithm, the formal semantics of the specification language had to be defined. The semantics has been used to prove in HOL the correctness of the transformations and to prove properties of the specification. We are currently building a system where a menu of useful andcorrectness preserving transformations will be available to the user. In this system the user could choose appropriate transformations from the menu taking advantage of his creativity and expertise to interactively guide the silicon compiler, without the risk of introducing inconsistencies. This article describes the formalmulti-rate semantics of a substantial subset of Silage and illustrates some formally verified transformations.     

S-semantics for logic programming: A retrospective look

The paper provides an overview of the s-semantic approach to the semantics of logic programs which had been developed about twenty years ago. The aim of such an approach was that of providing a suitable base for program analysis by means of a semantics which really captures the operational behavior of logic programs, and thus offers useful notions of observable program equivalences. The semantics is given in terms of extended interpretations, which are more expressive than Herbrand interpretations, extends the standard Herbrand semantics, and can be obtained as a result of both top-down and bottom-up constructions. The approach has been applied to several extensions of positive logic programs and used to develop semantic-based techniques for program analysis, verification and transformation.     

Inductive inference of logic programs based on algebraic semantics

In this paper we present a new inductive inference algorithm for a class of logic programs, calledlinear monadic logic programs. It has several unique features not found in Shapiro’s Model Inference System. It has been proved that a set of trees isrational if and only if it is computed by a linear monadic logic program, and that the rational set of trees is recognized by a tree automaton. Based on these facts, we can reduce the problem of inductive inference of linear monadic logic programs to the problem of inductive inference of tree automata. Further several efficient inference algorithms for finite automata have been developed. We extend them to an inference algorithm for tree automata and use it to get an efficient inductive inference algorithm for linear monadic logic programs. The correctness, time complexity and several comparisons of our algorithm with Model Inference System are shown.