Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-29T09:49:55.440Z Has data issue: false hasContentIssue false
  • English
  • Français

Mirror, mirror in my hand: a duality between specifications and models of process behaviour†

Published online by Cambridge University Press:  04 March 2009

J. L. Fiadeiro  and
J. F. Costa
J. L. Fiadeiro
Affiliation:
Department of Informatics, Faculty of Sciences, University of Lisbon, Campo Grande, 1700 Lisboa, Portugal Email {llf.fgc}@di.fc.ul.pt
J. F. Costa
Affiliation:
Department of Informatics, Faculty of Sciences, University of Lisbon, Campo Grande, 1700 Lisboa, Portugal Email {llf.fgc}@di.fc.ul.pt
Get access Rights & Permissions [Opens in a new window]

Summary

Since Pnueli’s seminal paper in 1977, Temporal Logic has been used as a formalism for specifying and verifying the correctness of reactive systems. In this paper, we show that, besides its expressive power, Temporal Logic enjoys a very strong structural property: it is categorical on processes. That is, we show how temporal specifications (as theories) can be embedded in categories of process behaviour, and out of this adjunction we build an institution that is categorical in the sense of Meseguer. This characterisation means that temporal logic is, in a sense, ‘sound and complete’ with respect to process specification and interconnection techniques.

Type
Research Article
Information
Mathematical Structures in Computer Science , Volume 6 , Issue 4 , August 1996 , pp. 353 - 373
Copyright
Copyright © Cambridge University Press 1996

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

Abadi, M. and Lamport, L. (1993) Composing Specifications, ACM TOPLAS 15 (1) 73–132.CrossRefGoogle Scholar
Barringer, H. (1987) The Use of Temporal Logic in the Compositional Specification of Concurrent Systems. In: Galton, A. (ed.) Temporal Logics and their Applications, Academic Press.Google Scholar
Chandy, K. M. and Misra, J. (1988) Parallel Program Design - A Foundation, Addison-Wesley.Google Scholar
Burstall, R. and Goguen, J. (1977) Putting Theories together to make Specifications. In: Reddy, R. (ed.) Proc Fifth International Joint Conference on Artificial Intelligence 1045–1058.Google Scholar
Costa, J. R., Sernadas, A., Sernadas, C. and Enrich, H.-D. (1992) Object Interaction, Mathematical Foundations of Computer Science. Springer- Verlag Lecture Notes in Computer Science 629 200–208.CrossRefGoogle Scholar
Dionisio, K. M. (1991) Um Modelo e Submodelos Categoriais de Processos Concorrentes, M.Sc. Thesis, Department of Mathematics, Faculty of Engineering, Technical University of Lisbon.Google Scholar
Ehrich, H.-D., Goguen, J. and Sernadas, A. (1991) A Categorial Theory of Objects as Observed Processes. In: deBakker, J., deRoever, W. and Rozenberg, G. (eds.) Foundations of Object-Oriented Languages. Springer-Verlag Lecture Notes in Computer Science 489 203–228.CrossRefGoogle Scholar
Fiadeiro, J. and Costa, J. F. (1993) Mirror, Mirror in My Hand: a Topological Adjunction between Temporal Theories and Processes, Research Report, DI-FCUL.Google Scholar
Fiadeiro, J. and Costa, J. F. (1995) Institutions for Behaviour Specification. In: Astesiano, E., Reggio, G. and Tarlecki, A. (eds.) Recent Trends in Data Type Specification. Springer-Verlag Lecture Notes in Computer Science 906 273–289.Google Scholar
Fiadeiro, J. and Maibaum, T. (1991) Describing, Structuring, and Implementing Objects. In: de-Bakker, J., de Roever, W. and Rozenberg, G. (eds.) Foundations of Object-Oriented Languages. Springer-Verlag Lecture Notes in Computer Science 489 274–310.CrossRefGoogle Scholar
Fiadeiro, J. and Maibaum, T. (1992) Temporal Theories as Modularisation Units for Concurrent System Specification. Formal Aspects of Computing 4 (3) 239–272.CrossRefGoogle Scholar
Fiadeiro, J., Costa, J. F., Sernadas, A. and Maibaum, T. (1993) Process Semantics of Temporal Logic Specification. In: Bidoit, M. and Choppy, C. (eds.) Proc. 8th Workshop on Data Type Specification, Dourdan, France, August 1991. Springer-Verlag Lecture Notes in Computer Science 655 236–253.CrossRefGoogle Scholar
Goguen, J. and Burstall, R. (1984) Introducing Institutions. In: Clarke, E. and Kozen, D. (eds.) Proc Logics of Programming Workshop. Springer-Verlag Lecture Notes in Computer Science 164 221–256.CrossRefGoogle Scholar
Goguen, J. and Ginali, S. (1978) A Categorical Approach to General Systems Theory. In: Klir, G. (ed.) Applied General Systems Research, Plenum 257–270.Google Scholar
Goldblatt, R. (1987) Logics of Time and Computation, CSLI.Google Scholar
Mac Lane, S. (1971) Categories for the Working Mathematician, Springer-Verlag.CrossRefGoogle Scholar
Manna, Z. and Pnueli, A. (1991) The Temporal Logic of Reactive and Concurrent Systems, Springer- Verlag.Google Scholar
Meseguer, J. (1989) General Logics. In: Ebbinghaus, H.-D.et al. (eds.) Logic Colloquium 87, North- Holland.Google Scholar
Misra, J. (1984) Reasoning about Networks of Communicating Processes. In: INRIA Advanced Nato Study Institute on Logics and Models for Verification and Specification of Concurrent Systems, Nice, France, Reidel.Google Scholar
Pnueli, A. (1977) The Temporal Logic of Programs. In: Proc 18th Annual Symposium on Foundations of Computer Science, IEEE 45–57.Google Scholar
Sassone, V., Nielsen, M. and Winskel, G. A. (1993) Classification of Models for Concurrency. In: Best, E. (ed.) CONCUR’93. Springer-Verlag Lecture Notes in Computer Science 715 82–96.CrossRefGoogle Scholar
Wolper, P. (1989) On the Relation of Programs and Computations to Models of Temporal Logic. In: Banieqbal, B., Barringer, H. and Pnueli, A. (eds.) Temporal Logic in Specification. Springer-Verlag Lecture Notes in Computer Science 398 75–123.CrossRefGoogle Scholar