Non-regular iterators in process algebra

We consider three forms of non-regular iteration in process algebra: the push-down operation $, defined by x$ y= x(( x$ y)( x$ y))+ y, the nesting operation ♯, defined by x ♯ y= x(( x ♯ y) x)+ y, and the back and forth operation ⇆, defined by x ⇆ y= x(( x ⇆ y) y)+ y. In the process algebraic framewo...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2001-10, Vol.269 (1), p.203-229
Main Authors: Bergstra, Jan A., Ponse, Alban
Format: Article
Language:English
Subjects:
Applied sciences
Back and forth operation
Computer science
control theory
systems
Concurrency
Exact sciences and technology
Expressiveness
Information systems. Data bases
Iteration
Kleene star
Memory organisation. Data processing
Nesting operation
Process algebra
Push-down operation
Software
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider three forms of non-regular iteration in process algebra: the push-down operation $, defined by x$ y= x(( x$ y)( x$ y))+ y, the nesting operation ♯, defined by x ♯ y= x(( x ♯ y) x)+ y, and the back and forth operation ⇆, defined by x ⇆ y= x(( x ⇆ y) y)+ y. In the process algebraic framework ACP with abstraction and one of $, ♯ or ⇆ we provide definitions of the following standard processes: stack, context-free process, bag, and queue. These definitions apply to all standard behavioural equivalences (we only use xτ= x, where τ is the silent step). Moreover, these results yield the expressive power to express computable processes modulo rooted branching bisimulation equivalence, and hence support the equational founding of process algebra: standard processes can be represented as terms.
ISSN:0304-3975
1879-2294
DOI:10.1016/S0304-3975(00)00413-8