Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-09T08:44:46.986Z Has data issue: false hasContentIssue false

Bisimulation on speed: Lower time bounds

Published online by Cambridge University Press:  15 July 2005

Gerald Lüttgen
Affiliation:
Department of Computer Science, The University of York, York YO10 5DD, UK; [email protected]
Walter Vogler
Affiliation:
Institut für Informatik, Universität Augsburg, 86135 Augsburg, Germany; [email protected]
Get access

Abstract

More than a decade ago, Moller and Tofts published their seminal work on relating processes, which are annotated with lower time bounds, with respect to speed. Their paper has left open many questions regarding the semantic theory for the suggested bisimulation-based faster-than preorder, the MT-preorder, which have not been addressed since. The encountered difficulties concern a general compositionality result, a complete axiom system for finite processes, a convincing intuitive justification of the MT-preorder, and the abstraction from internal computation. This article solves these difficulties by developing and employing a novel commutation lemma relating the sequencing of action and clock transitions in discrete-time process algebra. Most importantly, it is proved that the MT-preorder is fully-abstract with respect to a natural amortized preorder that uses a simple bookkeeping mechanism for deciding whether one process is faster than another. Together these results reveal the intuitive roots of the MT-preorder as a faster-than relation, while testifying to its semantic elegance. This lifts some of the barriers that have so far hampered progress in semantic theories for comparing the speed of processes.

Type
Research Article
Copyright
© EDP Sciences, 2005

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aceto, L., Ingólfsdóttir, A., Pedersen, M.L., and Poulsen, J., Characteristic formulae for timed automata. RAIRO-Theor. Inform. Appl. 34 (2000) 565584. CrossRef
Aceto, L. and Murphy, D., Timing and causality in process algebra. Acta Inform. 33 (1996) 317350. CrossRef
Alur, R. and Dill, D., A theory of timed automata. TCS 126 (1994) 183235. CrossRef
Arun-Kumar, S. and Hennessy, M.C.B., An efficiency preorder for processes. Acta Inform. 29 (1992) 737760. CrossRef
S. Arun-Kumar and V. Natarajan, Conformance: A precongruence close to bisimilarity, in STRICT '95, Workshops in Comp., Springer-Verlag (1995) 55–68.
Badouel, E. and Darondeau, P., On guarded recursion. TCS 82 (1991) 403408. CrossRef
J.C.M. Baeten and C.A. Middelburg, Process algebra with timing: Real time and discrete time, in Bergstra et al. [8], Chap. 10, 627–684.
J.A. Bergstra, A. Ponse and S.A. Smolka, editors, Handbook of Process Algebra. Elsevier Science (2001).
Cleaveland, R., Lüttgen, G. and Mendler, M., An algebraic theory of multiple clocks, in CONCUR '97, Springer-Verlag. Lect. Notes Comput. Sci. 1243 (1997) 166180. CrossRef
Cleaveland, R. and Sims, S., Concurrency Workbench, The NCSU, in CAV '96, Springer-Verlag. Lect. Notes Comput. Sci. 1102 (1996) 394397. CrossRef
Corradini, F., Gorrieri, R., and Roccetti, M., Performance preorder and competitive equivalence. Acta Inform. 34 (1997) 805835. CrossRef
Corradini, F., Vogler, W. and Jenner, L., Comparing the worst-case efficiency of asynchronous systems with PAFAS. Acta Inform. 38 (2002) 735792. CrossRef
De Nicola, R. and Hennessy, M.C.B., Testing equivalences for processes. TCS 34 (1984) 83133. CrossRef
Gorrieri, R., Roccetti, M. and Stancampiano, E., A theory of processes with durational actions. TCS 140 (1995) 7394. CrossRef
Hennessy, M.C.B. and Regan, T., A process algebra for timed systems. Inform. Comp. 117 (1995) 221239. CrossRef
C.A.R. Hoare, Communicating Sequential Processes. Prentice Hall (1985).
Jenner, L. and Vogler, W., Comparing the efficiency of asynchronous systems, in ARTS '99, Springer-Verlag. Lect. Notes Comput. Sci. 1601 (1999) 172191. CrossRef
Jenner, L. and Vogler, W., Fast asynchronous systems in dense time. TCS 254 (2001) 379422. CrossRef
G. Lüttgen and W. Vogler, Bisimulation on speed: Lower time bounds, in FOSSACS 2004, Springer-Verlag. Lect. Notes Comput. Sci. (2004).
R. Milner, Communication and Concurrency. Prentice Hall (1989).
Moller, F. and Tofts, C., A temporal calculus of communicating systems, in CONCUR '90, Springer-Verlag. Lect. Notes Comput. Sci. 458 (1990) 401415. CrossRef
Moller, F. and Tofts, C., Relating processes with respect to speed, in CONCUR '91, Springer-Verlag. Lect. Notes Comput. Sci. 527 (1991) 424438.
V. Natarajan and R. Cleaveland, An algebraic theory of process efficiency, in LICS '96, IEEE, Computer Society Press (1996) 63–72.
Schneider, S., An operational semantics for timed CSP. Inform. Comp. 116 (1995) 193213. CrossRef
Vogler, W., Faster asynchronous systems. Inform. Comput. 184 (2003) 311342. CrossRef