Merging regular processes by means of fixed-point theory
type: Item
instance of: scholarly article
title: Merging regular processes by means of fixed-point theory
zbMATH Open document ID: 0602.68025
DOI: 10.1016/0304-3975(86)90045-9
published in: Theoretical Computer Science
publication date: 1986-01-01T00:00:00Z
review text: First, we investigate a trace-set semantics of processes with \(\mu\)- recursion and arbitrary interleaving (merge). \(\mu\)-recursion is the analogue of recursion in standard programming by means of a recursive procedure. Iteration using while-statements can be viewed as a special case of this: so-called regular recursion. The semantics is used to support a formalism that determines the merge of two regular sequential (nondeterministic) processes. Next, we turn to processes with merge, \(\mu\)-recursion, and a second kind of recursion, called \(\alpha\)- recursion. This kind of recursion when applied in a regular forms is the equivalent of the Kleene-star iteration known from formal language theory. It involves only arbitrary big, but finite numbers of iterations. A different, more complicated framework is needed to give meaning to this kind of processes. Hereafter we define the semantics of the fair merge of these processes. Finally, we use this to prove the correctness of a formalism similar to the one for arbitrary merge in order to calculate the fair merge of two regular sequential (nondeterministic) processes with \(\mu\)-recursion.
Mathematics Subject Classification ID: 68N25
Mathematics Subject Classification ID: 68N01
zbMATH DE Number: 3972176
zbMATH Keywords: concurrency
zbMATH Keywords: fairness
zbMATH Keywords: denotational semantics
zbMATH Keywords: trace theory
zbMATH Keywords: infinite words
zbMATH Keywords: semantics of processes
zbMATH Keywords: recursion
zbMATH Keywords: interleaving
zbMATH Keywords: Iteration
zbMATH Keywords: while- statements
zbMATH Keywords: Kleene-star iteration
zbMATH Keywords: fair merge
zbMATH Keywords: correctness
author: John-Jules Meyer
MaRDI profile type: Publication
full work available at URL: 0304-3975(86)90045-9
OpenAlex ID: W2118347493
cites work: Q3939210
cites work: Q3917476
cites work: Countable nondeterminism and random assignment
cites work: A continuous semantics for unbounded nondeterminism
cites work: Q5181349
cites work: Q3899466
cites work: Linear time and branching time semantics for recursion with merge
cites work: Corrigendum: On infinite computations in denotational semantics
cites work: Processes and the denotational semantics of concurrency
cites work: Q3951525
cites work: Q3657410
cites work: Q3657421
cites work: Theory of \(\omega\)-languages. I: Characterizations of \(\omega\)-context- free languages
cites work: Q3667927
cites work: Semantics of nondeterminism, concurrency, and communication
cites work: A linear-history semantics for languages for distributed programming
cites work: On the existence of optimal fixpoints
cites work: A term model for synchronous processes
cites work: Q3883467
cites work: Q3907039
cites work: Q3657417
cites work: Fixed point theorems and semantics: A folk tale
cites work: Concurrent Processes and Their Syntax
cites work: A calculus of communicating systems
cites work: Q3857704
cites work: Q3906397
cites work: Q3907077
cites work: A Powerdomain Construction
cites work: Q3922147
cites work: Q3939206
cites work: Power domains
cites work: Effectively given domains
cites work: Q3316563
cites work: The Category-Theoretic Solution of Recursive Domain Equations
cites work: The \(\mu\)-calculus as an assertion-language for fairness arguments
cites work: Q3969890
cites work: A lattice-theoretical fixpoint theorem and its applications
description: scientific article; zbMATH DE number 3972176