Abstract
This paper is contributed to make connections between models for algebraic and temporal specifications. It brings a different viewpoint for classical algebras and algebraic specifications. Every algebra we concern here is finitely generated and associated with an implicit transition structure. The operators in the algebra may be partially defined. The class of algebras could be used as Kripke semantic models to interpret the temporals, so that we can do temporal reasoning about system behaviours such as safety and liveness properties. The unification of notions in algebraic and temporal specifications has many advantages for system developments. We may use a formal temporal deduction system to verify some dynamic properties from premises of algebraic specifications; or a temporal requirement specification may be used to develop systems in the style of top-down refinements. The notion of C-algebras has been crucial all along this work. In this paper we present the concepts, definitions and some basic theorems on C-algebras. Moreover, there exists a minimally defined algebra which is the initial one for each partially defined specification. The example of a lift controller is finally used to illustrate how to reason about the temporal behaviours of an algebraic specification.
This work is partly supported by the Commission of the European Communities under the ESPRIT Programme, Contract #390, PROSPECTRA Project.
On leave from University of Science & Technology of China, Hefei, Anhui 230026, China.
Preview
Unable to display preview. Download preview PDF.
References
J. Bergstra and J. Klop, Algebra of communicating processes with abstraction. TCS 37, 77–121, 1985.
J. Bergstra and J. Klop, Process Theory Based on Bisimulation Semantics, Report P8824 Univ. of Amsterdam, Holland, 1988.
M. Broy and M. Wirsing, Partial abstract types, Acta Informatica 18, 47–64, 1982.
M. Broy, Requirement and Design Specification for Distributed Systems, in F.Vogt ed., Proc. Concurrency 88, LNCS 335, Springer, 1988.
E. Clarke, E. Emerson and A. Sistla, Automatic verification of finite-state concurrent systems using temporal logic specifications, ACM Trans. on Prog. Languages and Systems, 8(2), 244–263, 1986.
H. Ehring, B. Mahr, Fundamentals of algebraic specification 1: Equations and initial semantics, EATCS Monographs on TCS, Springer, 1985.
Y. Feng, H. Lin and C.S.Tang, A proof system for temporal logic programs, Computer Research and Development (in Chinese), 22(10), 1985.
Y. Feng, X. Zhao and D. Guo, Modelling and verification of concurrent systems, J. of Computers, 13(1) (in Chinese), 1990.
C.A.R. Hoare, Communicating sequential processes, Comm. ACM 21(3), 1978.
S. Kaplan, Conditional rewrite rules, TCS 33, 175–193, 1984.
S. Kaplan, Algebraic specification of concurrent systems, TCS 69, 69–115, 1989.
H. Kreowski, Partial algebras flow from algebraic specifications, 14th ICALP proc., LNCS267, 521–530, 1987.
B. Krieg-Brückner, The PROSPECTRA methodology of program development, in J. Zalewski ed., Proc. IFIP/IFAC Working Conf. on Hardware and Software for Real Time Process Control, 1988.
F. Kroeger, Temporal Logic of Programs, EATCS Monographs on TCS, Springer, 1987.
L. Lamport, While waiting for the millennium: formal specification and verification of concurrent systems now, in F. Vogt ed., Proc. Concurrency 88, LNCS 335, Springer, 1988.
K. Larsen and L. Xinxin, Compositionality through an operational semantics of contexts. Tech. Report R89-13, Alborg Univ. Center, Denmark, 1989.
R. Milner, Calculus of Communicating Systems, LNCS 92, Springer, 1980.
R. Milner, Lecture on a calculus for communicating systems, Seminar on Concurrency, Carnegie Mellon Univ., LNCS 197, Springer, 1984.
A. Pnueli, Linear and branching structures in the semantics of logics and reactive systems, in Proc. 12th ICALP, LNCS 194, Springer, 1985.
A. Sernadas, J. Fiadeiro, C. Sernadas and H.Ehrich, Abstract object types: a temporal perspective, in B. Banieqbal, H. Barringer and A. Pnueli eds, Proc. Temporal logic in specifications, LNCS 398, Springer, 1989.
C. Zhou and C.A.R. Hoare, Partial corectness of communicating processes, in Proc. 2nd Intl. Conf. on Distributed Comput. Systems, Paris, 1981.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1990 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Feng, Y., Liu, J. (1990). A temporal approach to algebraic specifications. In: Baeten, J.C.M., Klop, J.W. (eds) CONCUR '90 Theories of Concurrency: Unification and Extension. CONCUR 1990. Lecture Notes in Computer Science, vol 458. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0039062
Download citation
DOI: https://doi.org/10.1007/BFb0039062
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-53048-0
Online ISBN: 978-3-540-46395-5
eBook Packages: Springer Book Archive