Logic in Computer Science (LICS 1991)

Paper: Actions speak louder than words: proving bisimilarity for context-free processes (at LICS 1991)

Authors: Hans Hüttel Colin Stirling

Abstract

J.C.M. Baeten et al. (Lecture Notes in Computer Science, vol. 259, pp. 93-114, 1987) proved that bisimulation equivalence is decidable for irredundant context-free grammars. A much simpler and much more direct proof of this result is provided now. It uses a tableau decision method involving goal-directed rules. The decision procedure yields an upper bound on a tableau depth. Moreover, it provides the essential part of the bisimulation relation between two processes which underlies their equivalence. A second virtue is that it provides a sound and complete equational theory for such processes

BibTeX

  @InProceedings{HttelStirling-Actionsspeakloudert,
    author = 	 {Hans Hüttel and Colin Stirling},
    title = 	 {Actions speak louder than words: proving bisimilarity for context-free processes },
    booktitle =  {Proceedings of the Sixth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1991},
    year =	 1991,
    editor =	 {Giles Kahn},
    month =	 {July}, 
    pages =      {376--386},
    location =   {Amsterdam, The Netherlands}, 
    publisher =	 {IEEE Computer Society Press}
  }