Author name cluster

C.A. Middelburg

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

TCS Journal 2020 Journal Article

On the complexity of the correctness problem for non-zeroness test instruction sequences

J.A. Bergstra
C.A. Middelburg

This paper concerns the question to what extent it can be efficiently determined whether an arbitrary program correctly solves a given problem. This question is investigated with programs of a very simple form, namely instruction sequences, and a very simple problem, namely the non-zeroness test on natural numbers. The instruction sequences concerned are of a kind by which, for each n > 0, each function from { 0, 1 } n to { 0, 1 } can be computed. The established results include the time complexities of the problem of determining whether an arbitrary instruction sequence correctly implements the restriction to { 0, 1 } n of the function from { 0, 1 } ⁎ to { 0, 1 } that models the non-zeroness test function, for n > 0, under several restrictions on the arbitrary instruction sequence.

Details DOI

I&C Journal 2010 Journal Article

A thread calculus with molecular dynamics

J.A. Bergstra
C.A. Middelburg

We present a theory of threads, interleaving of threads, and interaction between threads and services with features of molecular dynamics, a model of computation that bears on computations in which dynamic data structures are involved. Threads can interact with services of which the states consist of structured data objects and computations take place by means of actions which may change the structure of the data objects. The features introduced include restriction of the scope of names used in threads to refer to data objects. Because that feature makes it troublesome to provide a model based on structural operational semantics and bisimulation, we construct a projective limit model for the theory.

Details DOI

I&C Journal 2006 Journal Article

Splitting bisimulations and retrospective conditions

J.A. Bergstra
C.A. Middelburg

We investigate conditional expressions in the setting of ACP, an algebraic theory about processes. We introduce ACPc, an extension of ACP with conditional expressions in which the conditions are taken from a free Boolean algebra over a set of generators, and also its main models, called full splitting bisimilation models. We add two simple mechanisms for condition evaluation to ACPc; and we show their connection with state operators and signal emission, mechanisms from other extensions of ACP usable for condition evaluation. To allow for looking back on conditions under which preceding actions have been performed, we add a retrospection operator on conditions to ACPc. The choice of conditions forces us to introduce a new variant of bisimulation. However, without the generality implied by that choice, it would not have been possible to extend ACPc with retrospection. The addition of retrospection is a basic way to increase expressiveness.

Details DOI

TCS Journal 2005 Journal Article

Process algebra for hybrid systems

J.A. Bergstra
C.A. Middelburg

We propose a process algebra obtained by extending a combination of the process algebra with continuous relative timing from Baeten and Middelburg (Process Algebra with Timing, Springer, Berlin, 2002, Chapter 4), and the process algebra with propositional signals from Baeten and Bergstra (Theoret. Comput. Sci. 177 (1977) 381–405). The proposed process algebra makes it possible to deal with the behaviour of hybrid systems, i. e. systems in which the instantaneous state transitions caused by performing actions are alternated with continuous state evolutions. This process algebra has, in addition to equational axioms, rules to derive equations with the help of real analysis.

Details DOI