Citation
Eleftherios Matsikoudis, Edward A. Lee. "From Transitions to Executions". To appear in Proceedings of the Eleventh Workshop on Coalgebraic Methods in Computer Science (CMCS 2012), 2012.

Abstract
Interleaving theories have traditionally failed to integrate a satisfactory treatment of the so-called "finite delay property". This is generally attributed to the expansion law of such theories, but in truth, the problem is rooted in the concept of labelled transition system. We introduce a new type of system, in which, instead of labelled transitions, we have, essentially, sequences of labelled transitions. We call systems of this type labelled execution systems. We use a coalgebraic representation to obtain, in a canonical way, a suitable concept of bisimilarity among such systems, study the conditions under which that concept agrees with the intuitive understanding of equivalence of branching structure that one has for these systems, and examine their relationship with labelled transition systems, precisely characterizing the difference in expressive power and branching complexity between the two kinds of systems.

Electronic downloads

• http://coalg.org/cmcs12/papers/00010169.pdf

• HTML

  Eleftherios Matsikoudis, Edward A. Lee. <a
  href="http://chess.eecs.berkeley.edu/pubs/903.html"
  >From Transitions to Executions</a>, To appear in
  Proceedings of the Eleventh Workshop on Coalgebraic Methods
  in Computer Science (CMCS 2012), 2012.

• Plain text

  Eleftherios Matsikoudis, Edward A. Lee. "From
  Transitions to Executions". To appear in Proceedings of
  the Eleventh Workshop on Coalgebraic Methods in Computer
  Science (CMCS 2012), 2012.

• BibTeX

  @inproceedings{MatsikoudisLee12_FromTransitionsToExecutions,
      author = {Eleftherios Matsikoudis and Edward A. Lee},
      title = {From Transitions to Executions},
      booktitle = {To appear in Proceedings of the Eleventh Workshop
                on Coalgebraic Methods in Computer Science (CMCS
                2012)},
      year = {2012},
      abstract = {Interleaving theories have traditionally failed to
                integrate a satisfactory treatment of the
                so-called "finite delay property". This is
                generally attributed to the expansion law of such
                theories, but in truth, the problem is rooted in
                the concept of labelled transition system. We
                introduce a new type of system, in which, instead
                of labelled transitions, we have, essentially,
                sequences of labelled transitions. We call systems
                of this type labelled execution systems. We use a
                coalgebraic representation to obtain, in a
                canonical way, a suitable concept of bisimilarity
                among such systems, study the conditions under
                which that concept agrees with the intuitive
                understanding of equivalence of branching
                structure that one has for these systems, and
                examine their relationship with labelled
                transition systems, precisely characterizing the
                difference in expressive power and branching
                complexity between the two kinds of systems.},
      URL = {http://chess.eecs.berkeley.edu/pubs/903.html}
  }
  

Posted by Eleftherios Matsikoudis on 5 Apr 2012.
Groups: ptolemy
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.