Logic in Computer Science (LICS 1991)

Paper: On the relationship between process algebra and input/output automata (at LICS 1991)

Authors: Fritz W. Vaandrager

Abstract

The relationship between process algebra and input/output (I/O) automata models is investigated in a general setting of structured operational semantics. For a series of (approximations of) key properties of I/O automata, syntactic constraints on inference rules that guarantee these properties are proposed. A first result is that in a setting without assumptions about actions, trace and failure preorders are substitutive for any set of rules in a format due to R. de Simone (thesis, Univ. of Paris, 1984). Next, additional constraints that capture the notion of internal actions and guarantee substitutivity of the testing preorders of R. De Nicola and M. Hennessy (1984) and also of a preorder related to the failure semantics with fair abstraction of unstable divergence of J.A. Bergstra et al. (1988) are imposed. Subsequent constraints guarantee that input actions are always enabled and output actions cannot be blocked, two key features of I/O automata. The main result is that for any I/O calculus, i.e. a de Simone calculus that combines the constraints for internal, input and output actions, the quiescent trace preorder and the fair trace preorder are substitutive

BibTeX

  @InProceedings{Vaandrager-Ontherelationshipbe,
    author = 	 {Fritz W. Vaandrager},
    title = 	 {On the relationship between process algebra and input/output automata },
    booktitle =  {Proceedings of the Sixth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1991},
    year =	 1991,
    editor =	 {Giles Kahn},
    month =	 {July}, 
    pages =      {387--398},
    location =   {Amsterdam, The Netherlands}, 
    publisher =	 {IEEE Computer Society Press}
  }