Wyniki wyszukiwania - BazTech

1

Modelling and Analysing Qualitative Biological Models using Rewriting Logic

Alhumaidan A., Steggles J.

Fundamenta Informaticae

|

2017

|

Vol. 153, nr 1/2

1--28

EN

Qualitative logical modelling techniques play an important role in biology and are seen as crucial for developing scalable methods for modelling and synthesizing biological systems. While a range of interesting work has been done in this area there still exists challenging issues that need to be addressed for the practical application of these modelling techniques. In this paper we present an algebraic framework for exploring these issues by developing techniques for modelling and analysing qualitative biological models using Rewriting Logic (RL). The aim here is to develop a universal formal framework which is able to integrate models expressed in different formalisms (e.g. Boolean networks, Petri Nets and process algebra) and provide a basis for new work in this area (e.g. merging models based on different formalisms; compositional model construction and analysis; and tools for synthetic biology). We take as our starting point Multi-valued networks (MVNs), a simple yet expressive qualitative state based modelling approach widely used in biology. We develop a semantic translation from MVNs to a corresponding RL model and formally show that this translation is correct. We consider both the asynchronous and synchronous update semantics, and investigate the use of rewriting strategies to enable synchronisation to be modelled. We illustrate the RL framework developed and the potential RL analysis possible by presenting two detailed case studies.

2

Validating Behavioral Component Interfaces in Rewriting Logic

Johnsen E.B., Owe O., Torjusen A.B.

Fundamenta Informaticae

|

2008

|

Vol. 82, nr 4

341-359

EN

Many distributed applications can be understood in terms of components interacting in an open environment such as the Internet. Open environments are subject to change in unpredictable ways, as applications may arrive, evolve, or disappear. In order to validate components in such environments, it can be useful to build simulation environments which reflect this highly unpredictable behavior. This paper considers the validation of components with respect to behavioral interfaces. Behavioral interfaces specify semantic requirements on the observable behavior of components, expressed in an assume-guarantee style. In our approach, a rewriting logic model is transparently extended with the history of all observable communications, and metalevel strategies are used to guide the simulation of environment behavior. Over-specification of the environment is avoided by allowing arbitrary environment behavior within the bounds of the assumption on observable behavior, while the component is validated with respect to the guarantee of the behavioral interface.

3

The Open Calculus of Constructions (Part I) : An Equational Type Theory with Dependent Types for Programming, Specification, and Interactive Theorem Proving

Stehr M-O.

Fundamenta Informaticae

|

2005

|

Vol. 68, nr 1/2

131--174

EN

The open calculus of constructions integrates key features of Martin-Löf's type theory, the calculus of constructions, membership equational logic, and rewriting logic into a single uniform language. The two key ingredients are dependent function types and conditional rewriting modulo equational theories. We explore the open calculus of constructions as a uniform framework for programming, specification and interactive verification in an equational higher-order style. By having equational logic and rewriting logic as executable sublogics we preserve the advantages of a first-order semantic and logical framework and we provide a foundation for a broad spectrum of applications ranging from what could be called executable mathematics, involving symbolic computations and logical proofs, to software and system engineering applications, involving symbolic execution and analysis of nondeterministic and concurrent systems.

4

The Open Calculus of Constructions. Part 2, An Equational Type Theory with Dependent Types for Programming, Specification, and Interactive Theorem Proving

Stehr M.-O.

Fundamenta Informaticae

|

2005

|

Vol. 68, nr 3

249--288

EN

The open calculus of constructions integrates key features of Martin-Löf's type theory, the calculus of constructions, membership equational logic, and rewriting logic into a single uniform language. The two key ingredients are dependent function types and conditional rewriting modulo equational theories. We explore the open calculus of constructions as a uniform framework for programming, specification and interactive verification in an equational higher-order style. By having equational logic and rewriting logic as executable sublogics we preserve the advantages of a first-order semantic and logical framework and we provide a foundation for a broad spectrum of applications ranging from what could be called executable mathematics, involving symbolic computations and logical proofs, to software and system engineering applications, involving symbolic execution and analysis of nondeterministic and concurrent systems.

5

Revisiting the Algebra of Petri Net Processes under the Collective Token Philosophy

Coja-Oghlan A., Stehr M-O.

Fundamenta Informaticae

|

2003

|

Vol. 54, nr 2,3

151-164

EN

Revisiting the view of ``Petri nets as monoids'' suggested by Meseguer and Montanari, we give a direct proof of the well-known result that the class of Best/Devillers processes, which represents the behavior of Petri nets under the collective token semantics, has a sound and complete axiomatization in terms of symmetric monoidal categories. Using membership equational logic for the axiomatization, we prove the result by an explicit construction of a natural isomorphism between suitable functors. Our interest in the collective token semantics is motivated by earlier work on the use of rewriting logic as a uniform framework for different Petri net classes, especially including high-level Petri nets, where individuality of tokens can be already expressed at the system level.

6

Rule - based constraint programming

Kirchner C., Ringeissen C.

Fundamenta Informaticae

|

1998

|

Vol. 34, nr 3

225-262

EN

In this paper we present a view of constraint programming based on the notion of rewriting controlled by strategies. We argue that this concept allows to describe in a unified way the constraint solving mechanism as well as the meta-language needed to manipulate the constraints. This has the advantage to provide descriptions that are very close to the proof theoretical setting used now to describe constraint manipulations like unification or numerical constraint solving. We examplify the approach by presenting examples of constraint solvers descriptions and combinations written in the ELAN language.

7

Building Constraint Satisfaction Problem solvers using

Castro C.

Fundamenta Informaticae

|

1998

|

Vol. 34, nr 3

263-293

EN

In this paper, we formalize Constraint Satisfaction Problem manipulation using a rule-based approach. Based on the notion of Computational Systems, we associate basic transformations carried out by traditional constraint solving algorithms with rewrite rules, and heuristics with strategies establishing the order of application of the inferences. In this way, a constraint solver can be viewed as a computational system aimed to transform a set of constraints in a particular solved from. The distinction made between deduction rules and strategies, allows to describe constraint handling in a very abstract way, prototype new heuristics almost by modifying only the choice of rules, prove termination in an easier way, and combine constraint solving with other computational systems. To validate our approach we have implemented the system COLETTE which is currently executable in ELAN, an environment for prototyping computational systems. We have realized how easy it is to integrate and reuse solvers developed following this approach. We hope that this work leads the way to integrating the knowledge existing in the domain of Automated Deduction and Constraint Solving