Stream processing coalgebraically

We study various operations for splitting, partitioning, projecting and merging streams of data. These operations are motivated by their use in dataflow programming and stream processing languages. We use the framework of stream calculus and stream circuits for defining and proving properties of such operations using behavioural differential equations and coinduction proof principles. As a featured example we give proofs of results, observed by Moessner, from elementary number theory using our framework. We study the invariance of certain well patterned classes of streams, namely rational and algebraic streams, under splitting and merging. Finally we show that stream circuits extended with gates for dyadic split and merge are expressive enough to realise some non-rational algebraic streams, thereby going beyond ordinary stream circuits.     

Behavioural specification for hierarchical object composition

Behavioural specification based on hidden (sorted) algebra constitutes one of the most promising recently developed formal specification and verification paradigms for system development.Here we formally introduce novel concepts of behavioural object and equivalence between behavioural objects within the hidden algebra framework. We formally define several object composition operators on behavioural objects corresponding to the hierarchical object composition methodology introduced by CafeOBJ. We study their basic semantical properties and show that our most general form of behavioural object composition with synchronisation has final semantics and a composability property of behavioural equivalence supporting a high reusability of verifications. We also show the commutativity and the associativity of parallel compositions without synchronisation.     

Property specifications for workflow modelling

Previously we provided two formal behavioural semantics for the Business Process Modelling Notation (BPMN) in the process algebra CSP. By exploiting CSP’s refinement orderings, developers may formally compare their BPMN models. However, BPMN is not a specification language, and it is difficult and sometimes impossible to use it to construct behavioural properties against which other BPMN models may be verified. This paper considers a pattern-based approach to expressing behavioural properties. We describe a property specification language PL for capturing a generalisation of Dwyer et al.’s Property Specification Patterns, and present a translation from PL into a bounded, positive fragment of linear temporal logic, which can then be automatically translated into CSP for simple refinement checking. We present a detailed example studying the behavioural properties of an airline ticket reservation business process. Using the same example we also describe some recent results on expressing behavioural compatibility within our semantic models. These results lead to a compositional approach for ensuring deadlock freedom of interacting business processes.     

Reducibility of operation symbols in term rewriting systems and its application to behavioral specifications

In this paper, we propose the notion of reducibility of symbols in term rewriting systems (TRSs). For a given algebraic specification, operation symbols can be classified on the basis of their denotations: the operation symbols for functions and those for constructors. In a model, each term constructed by using only constructors should denote an element, and functions are defined on sets formed by these elements. A term rewriting system provides operational semantics to an algebraic specification. Given a TRS, a term is called reducible if some rewrite rule can be applied to it. An irreducible term can be regarded as an answer in a sense. In this paper, we define the reducibility of operation symbols as follows: an operation symbol is reducible if any term containing the operation symbol is reducible. Non-trivial properties of context-sensitive rewriting, which is a simple restriction of rewriting, can be obtained by restricting the terms on the basis of variable occurrences, its sort, etc. We confirm the usefulness of the reducibility of operation symbols by applying them to behavioral specifications for proving the behavioral coherence property.     

On the algebra of structured specifications

We develop module algebra for structured specifications with model oriented denotations. Our work extends the existing theory with specification building operators for non-protecting importation modes and with new algebraic rules (most notably for initial semantics) and upgrades the pushout-style semantics of parameterized modules to capture the (possible) sharing between the body of the parameterized modules and the instances of the parameters. We specify a set of sufficient abstract conditions, smoothly satisfied in the actual situations, and prove the isomorphism between the parallel and the serial instantiation of multiple parameters. Our module algebra development is done at the level of abstract institutions, which means that our results are very general and directly applicable to a wide variety of specification and programming formalisms that are rigorously based upon some logical system.     

Algebraic–coalgebraic specification in CoCasl

We introduce CoCasl as a light-weight but expressive coalgebraic extension of the algebraic specification language Casl. CoCasl allows the nested combination of algebraic datatypes and coalgebraic process types. Moreover, it provides syntactic sugar for an observer-indexed modal logic that allows e.g. expressing fairness properties. This logic includes a generic definition of modal operators for observers with structured equational result types. We prove existence of final models for specifications in a format that allows the use of equationally specified initial datatypes as observations, as well as modal axioms. The use of CoCasl is illustrated by specifications of the process algebras CSP and CCS.     

Exhaustive test sets for algebraic specifications

In the context of testing from algebraic specifications, test cases are ground formulas chosen amongst the ground semantic consequences of the specification, according to some possible additional observability conditions. A test set is said to be exhaustive if every programme P passing all the tests is correct and if for every incorrect programme P, there exists a test case on which P fails. Because correctness can be proved by testing on such a test set, it is an appropriate basis for the selection of a test set of practical size. The largest candidate test set is the set of observable consequences of the specification. However, depending on the nature of specifications and programmes, this set is not necessarily exhaustive. In this paper, we study conditions to ensure the exhaustiveness property of this set for several algebraic formalisms (equational, conditional positive, quantifier free and with quantifiers) and several test hypotheses. Copyright © 2016 John Wiley & Sons, Ltd.     

Algebraic Constructions: A Simple Framework for Complex Dependencies and Parameterisation

We propose a simple framework of algebraic constructions for software specification, modular design and development. Algebraic constructions generalise (parameterised) modules by allowing on one hand a rather arbitrary collection of elements to form the parameter and on the other hand dependencies between the module elements to be spelled out explicitly. Algebraic constructions are specified in a very natural way by means of ordinary algebraic specifications. They are combined using a sum operation which captures as special cases various operations on (parameterised) modules offered by standard specification and development frameworks. We show the expected composability result for the sum of algebraic constructions and of their specifications.     

CSP-CASL—A new integration of process algebra and algebraic specification

CSP–CASL integrates the process algebra CSP [T. Hoare, Communicating Sequential Processes, Prentice-Hall, Englewood cliffs, NJ, 1985; A.W. Roscoe, The Theory and Practice of Concurrency, Prentice-Hall, Englewood cliffs, NJ, 1998] with the algebraic specification language CASL [P.D. Mosses (Ed.), CASL Reference Manual, Lecture Notes in Computer Science, Vol. 2960, Springer, Berlin, 2004; E. Astesiano, M. Bidoit, B. Krieg-Brückner, H. Kirchner, P.D. Mosses, D. Sannella, A. Tarlecki, CASL—the common algebraic specification language, Theoret. Comput. Sci. 286 (2002) 153–196]. Its novel aspects include the combination of denotational semantics in the process part and, in particular, loose semantics for the data types covering both concepts of partiality and sub-sorting. Technically, this integration involves the development of a new so-called data-logic formulated as an institution. This data-logic serves as a link between the institution underlying CASL and the alphabet of communications necessary for the CSP semantics. Besides being generic in the various denotational CSP semantics, this construction leads also to an appropriate notion of refinement with clear relations to both data refinement in CASL and process refinement in CSP.     

From SOS Specifications to Structured Coalgebras: How to Make Bisimulation a Congruence

In this paper we address the issue of providing a structured coalgebra presentation of transition systems with algebraic structure on states determined by an equational specification Γ. More precisely, we aim at representing such systems as coalgebras for an endofunctor on the category of Γ-algebras. The systems we consider are specified by using a quite general format of SOS rules, the algebraic format, which in general does not guarantee that bisimilarity is a congruence.We first show that the structured coalgebra representation works only for systems where transitions out of complex states can be derived from transitions out of corresponding component states. This decomposition property of transitions indeed ensures that bisimilarity is a congruence. For a system not satisfying this requirement, next we propose a closure construction which adds context transitions, i.e., transitions that spontaneously embed a state into a bigger context or vice-versa. The notion of bisimulation for the enriched system coincides with the notion of dynamic bisimilarity for the original one, that is, with the coarsest bisimulation which is a congruence. This is sufficient to ensure that the structured coalgebra representation works for the systems obtained as result of the closure construction.     

Towards Behavioral Maude: Behavioral Membership Equational Logic

How can algebraic and coalgebraic specifications be integrated? How can behavioral equivalence be addressed in an algebraic specification language? The hidden-sorted approach, originating in work of Goguen and Meseguer in the early 80's, and further developed into the hidden-sorted logic approach by researchers at Oxford, UC San Diego, and Kanazawa offers some attractive answers, and has been implemented in both BOBJ and CafeOBJ. In this work we investigate both further extensions of hidden logic, and an extension of the Maude specification language called BMaude supporting this extended hidden-sorted semantics.Maude's underlying equational logic, membership equational logic, generalizes and increases the expressive power of many-sorted and order-sorted equational logics. We develop a hidden-sorted extension of membership equational logic, and give conditions under which theories have both an algebraic and a coalgebraic semantics, including final (co-)algebras. We also discuss the language design of BMaude, based on such an extended logic and using categorical notions in and across the different institutions involved. We also explain how Maude's reflective semantics provides a systematic method to extend Maude to BMaude within Maude, including module composition operations, evaluation, and automated proof methods.     

Behavioural approaches to algebraic specifications

This paper focuses on observability issues in the framework of loose algebraic specifications. The main purpose of observability is to extend the model class of some given algebraic specification in order to consider not only the algebras that satisfy the axioms of the specification in order to consider not only the algebras that satisfy the axioms of the specification, but as well other ones, provided that the differences between the properties satisfied by these algebras and the properties required by the specification (i.e., the axioms) are not “observable”. We compare various behavioural approaches developed so far. We point out their respective advantages and limitations. Expressive power is our main criterion for the discussion.     

Constructor-based observational logic

This paper focuses on the integration of reachability and observability concepts within an algebraic, institution-based framework. In the first part of this work, we develop the essential ingredients that are needed to define the constructor-based observational logic institution, called COL, which takes into account both the generation- and observation-oriented aspects of software systems. The underlying paradigm of our approach is that the semantics of a specification should be as loose as possible to capture all its correct realizations. We also consider the “black box” semantics of a specification which is useful to study the behavioral properties a user can observe when he/she is experimenting with the system.In the second part of this work, we develop proof techniques for structured COL-specifications. For this purpose we introduce an institution encoding from the COL institution to the institution of many-sorted first-order logic with equality and sort-generation constraints. Using this institution encoding, we can then reduce proofs of consequences of structured specifications built over COL to proofs of consequences of structured specifications written in a simple subset of the algebraic specification language Casl. This means, in particular, that any inductive theorem prover, such as e.g. the Larch Prover or PVS, can be used to prove theorems over structured COL-specifications.     

Behavioural equivalences and interference metrics for mobile ad-hoc networks

Connectivity and communication interference are two key aspects in mobile ad-hoc networks (MANETs). This paper proposes a process algebraic model targeted at the analysis of both such aspects. The framework includes a probabilistic process calculus and a suite of analytical techniques based on a probabilistic observational congruence and an interference-sensitive preorder. The former enables the verification of behavioural equivalences; the latter makes it possible to evaluate the interference level of behaviourally equivalent networks. The result is a comprehensive and effective framework for the behavioural analysis and a quantitative assessment of interference for wireless networks in the presence of node mobility. We show our techniques at work on two realistic case studies.     

Clifford and Graßmann Hopf algebras via the BIGEBRA package for Maple

Hopf algebraic structures will replace groups and group representations as the leading paradigm in forthcoming times. K-theory, co-homology, entanglement, statistics, representation categories, quantized or twisted structures as well as more geometric topics of invariant theory, e.g., the Graßmann-Cayley bracket algebra, are all covered by the Hopf algebraic framework. The new branch of experimental mathematics allows one to easily enter these fields through direct calculations using symbolic manipulation and computer algebra system (CAS). We discuss problems which were solved when building the BIGEBRA package for Maple and CLIFFORD to handle tensor products, Graßmann and Clifford algebras, coalgebras and Hopf algebras. Recent results showing the usefulness of CAS for investigating new and involved mathematics provide us with examples. An outlook on further developments is given.     

Stepwise Development of Process-Algebraic Specifications in Decorated Trace Semantics

Process algebras are convenient formalisms to develop specifications stepwise. This can be done with the help of partially defined states in a specification. When refining the specification, new transitions are added to partially defined states. At every step, it is verified with the help of special preorders, refinement relations, that the step leads towards a desired goal. This approach has already been introduced in the case, where the verification is based on weak bisimulation equivalence. We show in this article that refinement relations can also be developed in decorated trace semantics. Moreover, the intuitive picture seems to be simpler in trace-based than in bisimulation-based semantics. The algorithms to compute the new refinement relations are exponential in the worst case, but behave quite well in practical cases.     

An incremental approach to automatic algorithm design

This paper presents an incremental approach to automatic algorithm design,which can be described by algebraic specifications precisely and conveniently.The definitions of selection operator and extension operator which ca be defined by strategy relations and transformations are given in order to model the process of finding the solution of a problem.Also discussed is its object-oriented implementation.The functional specification and the design specification for an algorithm are given in one framework so that the correctness of the algorithm can be easily proved.