Eleventh Annual IEEE Symposium on

Logic in Computer Science (LICS 1996)

Paper: An Algebraic Theory of Process Efficiency (at LICS 1996)

Authors: V. Natarajan Rance Cleaveland


This paper presents a testing-based semantic theory for reasoning about the efficiency of concurrent systems as measured in terms of the amount of their internal activity. The semantic preorders are given an algebraic characterization, and their optimality is established by means of a full abstractness result. They are also shown to subsume existing bisimulation-based efficiency preorders. An example is provided to illustrate the utility of this approach.


    author = 	 {V. Natarajan and Rance Cleaveland},
    title = 	 {An Algebraic Theory of Process Efficiency},
    booktitle =  {Proceedings of the Eleventh Annual IEEE Symp. on Logic in Computer Science, {LICS} 1996},
    year =	 1996,
    editor =	 {Edmund M. Clarke},
    month =	 {July}, 
    pages =      {63-72},
    location =   {New Brunswick, NJ, USA}, 
    publisher =	 {IEEE Computer Society Press}