Abstract
The Mean-Value Calculus, MVC, of Zhou and Li [19] is extended with the least and the greatest fixed point operators. The resulting logic is called μMVC. Timed behaviours with naturally recursive structure can be elegantly specified in this logic. Some examples of such usage are given. The expressive power of the logic is also studied. It is shown that the propositional fragment of the logic, even with discrete time, is powerful enough to encode the computations of nondeterministic turing machines. Hence, the satisfiability of propositional μMVC over both dense and discrete times is undecidedable.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alur, R., Henzinger, T.A.: A Really Temporal Logic. Jour. ACM 41(1) (1994)
Banieqbal, B., Barringer, H.: Temporal Logic with Fixed Points. In: Banieqbal, B., Pnueli, A., Barringer, H. (eds.) Temporal Logic in Specification. LNCS, vol. 398. Springer, Heidelberg (1989)
Emerson, E.: Real-time and the Mu Calculus. In: Huizing, C., de Bakker, J.W., Rozenberg, G., de Roever, W.-P. (eds.) REX 1991. LNCS, vol. 600. Springer, Heidelberg (1992)
Emerson, E., Clarke, E.: Characterising Correctness Properties of Parallel Programs using Fixed-points. In: de Bakker, J.W., van Leeuwen, J. (eds.) ICALP 1980. LNCS, vol. 85. Springer, Heidelberg (1980)
Hansen, M.R., Pandya, P.K.: Zhou Chaochen. Finite Divergence. Theoretical Computer Science 138, 113–139 (1994)
Hansen, M.R., Zhou, C.: Chaochen Zhou. Duration calculus: Logical foundations. Formal Aspects of Computing 9(3), 283–330 (1997)
Kozen, D.: Results on Propositional Mu-calculus. Thoeretical Computer Science 27, 333–354 (1983)
Li, X.: A Mean Value Calculus. Ph.D. Thesis, Software Institute, Academia Sinica (1994)
Moszkowski, B.: A Temporal Logic for Multi-level Reasoning about Hardware. IEEE Computer 18(2), 10–19 (1985)
Pandya, P.K.: Some Extensions to Mean-Value Calculus: Expressiveness and Decidability. In: Kleine Büning, H. (ed.) CSL 1995. LNCS, vol. 1092. Springer, Heidelberg (1996)
Pandya, P.K., Hung, D.V.: Duration Calculus of Weakly Monotonic Time. In: Ravn, A.P., Rischel, H. (eds.) FTRTFT 1998. LNCS, vol. 1486, p. 55. Springer, Heidelberg (1998)
Pandya, P.K., Ramakrishna, Y.S.: A Recursive Mean Value Calculus. Technical Report TCS-95/3, Computer Science Group, TIFR, Bombay (1995)
Pandya, P.K., Ramakrishna, Y.S., Shyamasundar, R.K.: A Compositional Semantics of Esterel in Duration Calculus. In: Proc. Second AMAST workshop on Real-time Systems: Models and Proofs, Bordeux (June 1995)
Pandya, P.K., Wang, H., Xu, Q.: Towards a Theory of Sequential Hybrid Programs. In: de Roever, W.P., Gries, D. (eds.) Proc. PROCOMET 1998, Shelter Island, New York. Chapman & Hall, Boca Raton (1998)
Skakkebaek, J.U., Shankar, N.: Towards a Duration Calculus Proof Assistant in PVS. In: Langmaack, H., de Roever, W.-P., Vytopil, J. (eds.) FTRTFT 1994 and ProCoS 1994. LNCS, vol. 863. Springer, Heidelberg (1994)
Stirling, C.: Modal and Temporal logics. In: Handbook of Logic in Computer Science, vol. 2, pp. 476–563. Clarendon Press, Oxford (1995)
Schneider, G., Xu, Q.: Towards Formal Semantics of Verilog using Duration Calculus. In: Ravn, A.P., Rischel, H. (eds.) FTRTFT 1998. LNCS, vol. 1486, p. 282. Springer, Heidelberg (1998)
Zhou, C., Hoare, C.A.R., Ravn, A.P.: A Calculus of Durations. Information Processing Letters 40(5), 269–276 (1991)
Zhou, C., Li, X.: A Mean Value Calculus of Durations. In: Roscoe, A.W. (ed.) A Classical Mind: Essays in Honour of C.A.R. Hoare, pp. 431–451. Prentice Hall International, Englewood Cliffs (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pandya, P.K., Ramakrishna, Y.S. (1998). Recursive Mean-Value Calculus. In: Arvind, V., Ramanujam, S. (eds) Foundations of Software Technology and Theoretical Computer Science. FSTTCS 1998. Lecture Notes in Computer Science, vol 1530. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-49382-2_23
Download citation
DOI: https://doi.org/10.1007/978-3-540-49382-2_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65384-4
Online ISBN: 978-3-540-49382-2
eBook Packages: Springer Book Archive