Wyniki wyszukiwania - BazTech

1

Simulation Opacity

Gruska D. P.

Fundamenta Informaticae

|

2014

|

Vol. 133, nr 2/3

165--179

EN

Opacity testing is formalized and studied. We specify opacity testers as well as tested systems by (timed) process algebras. We model various testers according to how sophisticated observations of tested system they can make and which kind of conclusions they can obtain. We use this technique to define several realistic security properties. The properties are studied and compared with other security concepts.

2

Formal Analysis of SystemC Designs in Process Algebra

Hojjat H., Mousavi M. R., Sirjani M.

Fundamenta Informaticae

|

2011

|

Vol. 107, nr 1

19-42

EN

SystemC is an IEEE standard system-level language used in hardware/software co-design and has been widely adopted in the industry. This paper describes a formal approach to verifying SystemC designs by providing a mapping to the process algebra mCRL2. Our mapping formalizes both the simulation semantics as well as exhaustive state-space exploration of SystemC designs. By exploiting the existing reduction techniques of mCRL2 and also its model-checking tools, we efficiently locate the race conditions in a system and resolve them. A tool is implemented to automatically perform the proposed mapping. This mapping and the implemented tool enabled us to exploit process-algebraic verification techniques to analyze a number of case-studies, including the formal analysis of a single-cycle and a pipelined MIPS processor specified in SystemC.

3

PSF - A Retrospective

Veltin G.J.

Fundamenta Informaticae

|

2010

|

Vol. 100, nr 1/4

181-227

EN

Modern day computer architectures offer ever-increasing support for parallel processing, still it turns out to be quite difficult for programmers and therefore programs to tap into these parallel resources. To benefit from real general-purpose parallel computing we claim that it is likely that a paradigm shift is needed in the way we think about programming. This change of thought in turn will need to be reflected in future programming languages as well. We think that the field of process algebra provides thorough insight in how to reason about the construction of software for concurrent systems and will be one of the enabling technologies supporting this transition. The wish to connect process algebra, a mathematical theory, to the world of computer-readable and executable specifications led to the development of PSF (Process Specification Formalism). PSF is an implementation of the process algebra ACP (Algebra of Communicating Processes) integrating ASF (Algebraic Specification Formalism) to specify algebraic data types. One of the first publications on PSF appeared in Fundamenta Informaticae in 1990. Here we stated as the first sentence of the abstract: "Traditional methods for programming sequential machines are inadequate for specifying parallel systems". Unfortunately, though some advancements have been made since 1990, we can still uphold this statement 20 years later. This current report documents the developments that lead to the construction of PSF and the 1990 publication and moreover it also documents how PSF and its tools have evolved since 1990 taking the conclusion and the outlook for future work from the original article as a reference point. Using the knowledge gained both in constructing tools for PSF and in using PSF to specify concurrent systems, we will judge, discuss and criticise the design decisions taken and show paths for future developments.

4

An Interface Group for Process Components

Bergstra J.A., Middelburg C.A.

Fundamenta Informaticae

|

2010

|

Vol. 99, nr 4

335-382

EN

We take a process component as a pair of an interface and a behaviour. We study the composition of interacting process components in the setting of process algebra. We formalize the interfaces of interacting process components by means of an interface group. An interesting feature of the interface group is that it allows for distinguishing between expectations and promises in interfaces of process components. This distinction comes into play in case components with both client and server behaviour are involved.

5

Paradigms of Denotational Mathematics for Cognitive Informatics and Cognitive Computing

Wang Y.

Fundamenta Informaticae

|

2009

|

Vol. 90, nr 3

283-303

EN

The abstract, rigorous, and expressive needs in cognitive informatics, intelligence science, software science, and knowledge science lead to new forms of mathematics collectively known as denotational mathematics. Denotational mathematics is a category of expressive mathematical structures that deals with high level mathematical entities beyond numbers and sets, such as abstract objects, complex relations, behavioral information, concepts, knowledge, processes, and systems. Denotational mathematics is usually in the form of abstract algebra that is a branch of mathematics in which a system of abstract notations is adopted to denote relations of abstract mathematical entities and their algebraic operations based on given axioms and laws. Four paradigms of denotational mathematics, known as concept algebra, system algebra, Real-Time Process Algebra (RTPA), and Visual Semantic Algebra (VSA), are introduced in this paper. Applications of denotational mathematics in cognitive informatics and computational intelligence are elaborated. Denotational mathematics is widely applicable to model and manipulate complex architectures and behaviors of both humans and intelligent systems, as well as long chains of inference processes.

6

On Process-algebraic Verification of Asynchronous Circuits

Wang X., Kwiatkowska M.

Fundamenta Informaticae

|

2007

|

Vol. 80, nr 1-3

283-310

EN

Asynchronous circuits have received much attention recently due to their potential for energy savings. Process algebras have been extensively used in the modelling, analysis and synthesis of asynchronous circuits. This paper develops a theoretical basis for using process algebra and associated model checking tools to verify asynchronous circuits. We formulate a model that extends existing verification theory for asynchronous circuits, and integrate it into the framework of standard process algebra theory. Our theory permits analysis of safeness (i.e. choke) and progress (i.e. illegal stop, divergence and relative starvation) conditions. We show how the model can be translated into CSP, and how the satisfaction of safeness and progress requirements can be reduced to refinement checks in CSP. Finally, the correspondence of our theory with trace theory (i.e. prefix-closed trace structures), receptive process theory and the XDI model is investigated.

7

Observation Based System Security

Gruska D.P.

Fundamenta Informaticae

|

2007

|

Vol. 79, nr 3-4

335-346

EN

A formal model for description of passive and active timing attacks is presented, studied and compared with other security concepts. It is based on a timed process algebra and on a concept of observations which make only a part of system behaviour visible. From this partial information which contains also timing of actions an intruder tries to deduce some private system activities.

8

Controllable Delay-Insensitive Processes

Josephs M.B., Kapoor H.K.

Fundamenta Informaticae

|

2007

|

Vol. 78, nr 1

101-130

EN

Josephs and Udding's DI-Algebra offers a convenient way of specifying and verifying designs that must rely upon delay-insensitive signalling between modules (asynchronous logic blocks). It is based on Hoare's theory of CSP, including the notion of refinement between processes, and is similarly underpinned by a denotational semantics. Verhoeff developed an alternative theory of delay-insensitive design based on a testing paradigm and the concept of reflection. The first contribution of this paper is to define a relation between processes in DI-Algebra that captures Verhoeff's notion of a closed system passing a test (by being free of interference and deadlock). The second contribution is to introduce a new notion of controllability, that is, to define what it means for a process to be controllable in DI-Algebra. The third contribution is to extend DI-Algebra with a reflection operator and to show how testing relates to controllability, reflection and refinement. It is also shown that double reflection yields fully-abstract processes in the sense that it removes irrelevant distinctions between controllable processes. The final contribution is a modified version of Verhoeff's factorisation theorem that could potentially be of major importance for constructive design and the development of design tools. Several elementary examples are worked out in detail to illustrate the concepts. The claims made in this paper are accompanied by formal proofs, mostly in an annotated calculational style.

9

Verification and Implementation of Delay-Insensitive Processes in Restrictive Environments

Kapoor H.K., Josephs M.B., Furey D.P.

Fundamenta Informaticae

|

2006

|

Vol. 70, nr 1,2

21-48

EN

A delay-insensitive module communicates with its environment through wires of unbounded delay. To avoid transmission interference, the absorption of a signal transition must be acknowledged before another one is propagated along the same wire. The environment may guarantee, however, to interact with the module in an even more restrictive way. It is worthwhile taking this into account when synthesising the module because it may allow for a cheaper, faster implementation. The concept of restriction has been built into our translation tool, di2pn (to help in synthesis), and our analysis tool, diana (to perform equivalence and refinement checking). Formally, DI-Algebra is equipped with a new operator that weakens the specification of a module by taking its environment into account. This operator is a useful instance of divergence extension, a concept introduced by Mallon. Divergence extension in general, and restriction and alternation in particular, can be represented with the parallel composition operator and so are amenable to algebraic reasoning.

10

Thread Algebra with Multi-Level Strategies

Bergstra J.A., Middelburg C.A.

Fundamenta Informaticae

|

2006

|

Vol. 71, nr 2,3

153-182

EN

In a previous paper, we developed an algebraic theory about threads and multi-threading based on the assumption that a deterministic interleaving strategy determines how threads are interleaved. The theory includes interleaving operators for a number of plausible deterministic interleaving strategies. The interleaving of different threads constitutes a multi-thread. Several multi-threads may exist concurrently on a single host in a network, several host behaviors may exist concurrently in a single network on the internet, etc. In the current paper, we assume that the above-mentioned kind of interleaving is also present at these other levels. We extend the theory developed so far with features to cover the multi-level case. We use the resulting theory to develop a simplified formal representation schema of systems that consist of several multi-threaded programs on various hosts in different networks. We also investigate the connections of the resulting theory with the algebraic theory of processes known as ACP.

11

Note on Some Order Properties Related to Processes Semantics (I)

Vaida D.

Fundamenta Informaticae

|

2006

|

Vol. 73, nr 1-2

307-319

EN

This note begins a study of some elementary properties related to the order structures applied in the algebraic approach to processes semantics. The support examples come from the partially additive semantics developed by Steenstrup (1985) and Manes and Arbib (1986) and from process algebra of Baeten and Weijland (1990). The main sources for the algebraic theory are F.A.Smith (1966) and Golan (1999). We show that different properties can be extended to partially additive distributive algebras more general than sum-ordered partial semirings. One establishes that the support examples constitute multilattices, in the sense of Benado (1955). By the examples, the ordering considered, and the references, this preliminary study is related to Rudeanu et al. (2004) and to the algebraic approach to languages due to Mateescu, e.g., (1996), (1989), (1994).

12

Zastosowanie języka LOTOS do modelowania wybranych struktur metody HOOD

Brzuchcz R.

Elektrotechnika i Elektronika

|

2006

|

T. 25, z. 1

1-9

PL

W pracy zaprezentowano możliwości użycia języka LOTOS [3, 7] w projektowaniu oprogramowania systemów czasu rzeczywistego metodą HOOD [6, 13]. Wybrane struktury HOOD zostają wyrażone w języku algebry procesów i abstrakcyjnych typów danych, co zapewnia możliwość formalnej analizy tworzonego projektu. We wprowadzeniu do pracy wyjaśniono cel i motywacje do tworzenia modelu formalnego projektu systemu czasu rzeczywistego. Następnie przedstawiono skrócony opis metodyki hierarchicznego projektowania HOOD, której notacja i proces projektowy stanowią bazę dla proponowanej metody formalizacji. Wyjaśniono znaczenie takich konstrukcji, jak moduł, interfejs, operacja, hierarchia użycia i zawierania. W kolejnym punkcie, po krótkim przedstawieniu języka LOTOS [3, 7], zaprezentowano technikę, w której konstrukcje metody HOOD zostają zinterpretowane w języku formalnym algebry procesów i abstrakcyjnych typów danych. Opis przeprowadzony jest dla prostego przykładu projektu w HOOD, celem wyjaśnienia istoty interpretacji. W części końcowej pracy podano wnioski wraz ze wskazaniem dalszych możliwych kierunków rozwoju i zastosowań prezentowanej metody.

EN

The article presents a possibility of using LOTOS [3, 7] formal language in the HOOD [6, 13] real-time system design. Process algebras and abstract data types are used to express some HOOD structures in order to allow formal analysis of the system. The introduction explains the motivations and the goal of the work. Then, there is a brief survey of the HOOD hierarchical design method in the next point. It states as the base for the formalization method explained in the article. The notions of module, interface, operation, use and include relations are briefly explained. After it, the simple LOTOS language constructs are also presented. Next point explains the formalization of the HOOD structures. This is the most essentials part of the work where the method is presented on the exemplary HOOD diagram. LOTOS code is produced relate to the HOOD informal semantic. It expresses the main concepts of the HOOD dynamic model. There are the conclusions and further works proposals at the end of the article.

13

Logical Analysis of Biological Systems

Mardare R., Priami C.

Fundamenta Informaticae

|

2005

|

Vol. 64, nr 1-4

275-289

EN

Our paper proposes a technique for performing logical analysis over the calculi for communication and mobility, i.e., Ambient Calculus type of calculi. We show how this analysis can be used in the case of biological models in order to obtain significant information for biologists. The technique is based on set theoretical models we developed for ambient processes by using the power of Hypersets Theory. These models are further used as possible worlds in a Kripke structure organized for a propositional branching temporal logic. Providing the temporal logical structure for the accessibility relation between ambient processes, we open the perspective of reusing model checking algorithms developed for temporal logics in analyzing any phenomena that can be described by these calculi.

14

Event Structures for Arbitrary Disruption

Fecher H., Majster-Cederbaum M.

Fundamenta Informaticae

|

2005

|

Vol. 68, nr 1/2

103--130

EN

In process algebras that allow for some form of disruption, it is important to state when a process terminates. One option is to include a termination action Ö. Another approach is that the `final' executed action of a process terminates the process. The semantics of the former approach has been investigated in the literature in detail, e.g. by providing consistent true-concurrency and operational descriptions. The `final' executed action termination approach, which is more adequate for modelling, still lacks the existence of a detailed true concurrent description. In order to give a true concurrency model of such a termination view, we introduce a new class of event structures. This type of event structures models disabling by indicating sets of precursor events. We show that the introduced class of event structures has more expressive power with respect to event traces than the common event structures. We also give a classification of the expressive power in terms of sets of event traces. A consistency result of an operational and a denotational semantics is shown.

15

$-Calculus of Bounded Rational Agents : Flexible Optimization as Search under Bounded Resources in Interactive Systems

Eberbach E.

Fundamenta Informaticae

|

2005

|

Vol. 68, nr 1/2

47--102

EN

This paper presents a novel model for resource bounded computation based on process algebras. Such model is called the $-calculus (cost calculus). Resource bounded computation attempts to find the best answer possible given operational constraints. The $-calculus provides a uniform representation for optimization in the presence of limited resources. It uses cost-optimization to find the best quality solutions while using a minimal amount of resources. A unique aspect of the approach is to propose a resource bounded process algebra as a generic problem solving paradigm targeting interactive AI applications. The goal of the $-calculus is to propose a computational model with built-in performance measure as its central element. This measure allows not only the expression of solutions, but also provides the means to incrementally construct solutions for computationally hard, real-life problems. This is a dramatic contrast with other models like Turing machines, l-calculus, or conventional process algebras. This highly expressive model must therefore be able to express approximate solutions. This paper describes the syntax and operational cost semantics of the calculus. A standard cost function has been defined for strongly and weakly congruent cost expressions. Example optimization problems are given which take into account the incomplete knowledge and the amount of resources used by an agent. The contributions of the paper are twofold: firstly, some necessary conditions for achieving global optimization by performing local optimization in time and/or space are found. That deals with incomplete information and complexity during problem solving. Secondly, developing an algebra which expresses current practices, e.g., neural nets, cellular automata, dynamic programming, evolutionary computation, or mobile robotics as limiting cases, provides a tool for exploring the theoretical underpinnings of these methods. As the result, hybrid methods can be naturally expressed and developed using the algebra.

16

Semirings in Operations Research and Computer Science: More Algebra

Rudeanu S., Vaida D.

Fundamenta Informaticae

|

2004

|

Vol. 61, nr 1

61--85

EN

We undertake an axiomatic study of certain semirings and related structures that occur in operations research and computer science. We focus on the properties A,I,U,G,Z,L that have been used in the algebraic study of path problems in graphs and prove that the only implications linking the above properties are essentially those already known. On the other hand we extend those implications to the framework of left and right variants of A,I,U,G,Z,L, and we also prove two embedding theorems. Further generalizations refer mainly to semiring-like algebras with a partially defined addition, which is needed in semantics. As suggested by idempotency (I) and absorption (A), we also examine in some detail the connections between semirings and distributive lattices, which yield new systems of axioms for the latter.

17

Located Actions in Process Algebra with Timing

Bergstra J.A., Middelburg C.A.

Fundamenta Informaticae

|

2004

|

Vol. 61, nr 3,4

183--211

EN

We propose a process algebra obtained by adapting the process algebra with continuous relative timing from Baeten and Middelburg [Process Algebra with Timing, Springer, 2002, Chap. 4] to spatially located actions. This process algebra makes it possible to deal with the behaviour of systems with a known time-dependent spatial distribution, such as protocols transmitting data via a mobile intermediate station. It is a reformulation of the real space process algebra from Baeten and Bergstra [Formal Aspects of Computing, 5, 1993, 481-529] in a setting with urgent actions. This leads to many simplifications.

18

Asynchronous Box Calculus

Devillers R., Klaudel H., Koutny M., Pommereau F.

Fundamenta Informaticae

|

2003

|

Vol. 54, nr 4

295-344

EN

The starting point of this paper is an algebraic Petri net framework allowing one to express net compositions, such as iteration and parallel composition, as well as transition synchronisation and restriction. We enrich the original model by introducing new constructs supporting asynchronous interprocess communication. Such a communication is made possible thanks to special `buffer' places where different transitions (processes) may deposit and remove tokens. We also provide an abstraction mechanism, which hides buffer places, effectively making them private to the processes communicating through them. We then provide an algebra of process expressions, whose constants and operators directly correspond to those used in the Petri net framework. Such a correspondence is used to associate nets to process expressions in a compositional way. That the resulting algebra of expressions is consistent with the net algebra is demonstrated by showing that an expression and the corresponding net generate isomorphic transition systems. This results in the Asynchronous Box Calculus (or ABC), which is a coherent dual model, based on Petri nets and process expressions, suitable for modelling and analysing distributed systems whose components can interact using both synchronous and asynchronous communication.

19

Process Algebra with Nonstandard Timing

Middelburg K.A.

Fundamenta Informaticae

|

2002

|

Vol. 53, nr 1

55-77

EN

The possibility of two or more actions to be performed consecutively at the same point in time is not excluded in the process algebras from the framework of process algebras with timing presented by Baeten and Middelburg [Handbook of Process Algebra, Elsevier, 2001, Chapter 10]. This possibility is useful in practice when describing and analyzing systems in which actions occur that are entirely independent. However, it is an abstraction of reality to assume that actions can be performed consecutively at the same point in time. In this paper, we propose a process algebra with timing in which this possibility is excluded, but nonstandard non-negative real numbers are included in the time domain. It is shown that this new process algebra generalizes the process algebras with timing from the aforementioned framework in a smooth and natural way.

20

Modeling Dynamic Objects in Distributed Systems with Nested Petri Nets

Lomazova I.A.

Fundamenta Informaticae

|

2002

|

Vol. 51, nr 1,2

121-133

EN

Nested Petri nets (NP-nets) is a Petri net extension, allowing tokens in a net marking to be represented by marked nets themselves. The paper discusses applicability of NP-nets for modeling task planning systems, multi-agent systems and recursive-parallel systems. A comparison of NP-nets with some other formalisms, such as OPNs of R. Valk, recursive parallel programs of O. Kushnarenko and Ph. Schnoebelen and process algebras is given. Some aspects of decidability for object-oriented Petri net extensions are also discussed.