Abstract
In this paper we analyze a program of a software/hardware system using explicit rational time. The analysis is based on v-conversion, which interprets programs with rational time, and tense arithmetic. As a typical example we adopt a kind of bounded buffer problem, in which a producer sends data to a consumer with a bounded buffer, but the producer cannot examine status of the buffer. How to send data as fast as possible without overflowing the buffer is a problem. Properties of a program of the system are analyzed and safety conditions that the buffer does not overflow are obtained.
Preview
Unable to display preview. Download preview PDF.
References
Chaochen, Z., Hoare, C. A. R. and Ravn, P.: A Calculus of Durations, Inf. Process. Lett., Vol. 40, pp.269–276 (1991).
Cousot, P.: Methods and Logics for Proving Programs, J. van Leeuwen, ed., Handbook of Theoretical Computer Science (1990).
Gao, T., Hosono, C. and Yamanaka, K.: An Analytic Semantics of CSP, Fundamenta Informaticae, Vol. 15, No. 2, pp.107–122 (1991).
Hoare, C. A. R.: An Axiomatic Basis for Computer Programming, Comm. ACM, Vol. 12, No. 10, pp.576–580,583 (1969).
Hoare, C. A. R.: Communicating Sequential Processes, Comm. ACM, Vol. 21, No. 8, pp.666–677 (1978).
Hoare, C. A. R.: Communicating Sequential Processes, Prentice-Hall International (1985).
Igarashi, S.: The v-conversion and an Analytic Semantics, R. E. A. Mason, ed., Inf. Proc., IFIP, Elsevier Science Publishers B. V.(North-Holland), pp.769–774 (1983).
Igarashi, S., Mizutani, T. and Tsuji, T.: An Analytical Semantics of Parallel Program Processes Represented by v-conversion, TENSOR, N. S. Vol. 45, pp.222–228 (1987).
Igarashi, S., Mizutani, T. and Tsuji, T.: Specifications of Parallel Program Processes in Analytical Semantics, TENSOR, N. S. Vol. 45, pp.240–244 (1987).
Igarashi, S., Tsuji, T., Mizutani, T. and Haraguchi, T.: Experiments on Computerized Piano Accompaniment, Proceedings of the 1993 International Computer Music Conference, pp.415–417 (1993).
Ikeda Y.: An interpreter of the higher typed logical programming language NU, Ph.D. Thesis, University of Tsukuba (in Japanese) (1993).
Kröger, F.: Temporal Logic of Programs, Springer-Verlag (1987).
Lamport, L.: What Good is Temporal Logic?, R. E. A. Mason, ed., Inf. Proc., IFIP, Elsevier Science Publishers B. V.(North-Holland), pp.657–668 (1983).
Milner, R.: A Calculus of Communicating Systems, LNCS 92, Springer-Verlag (1980).
Milner, R.: Communication and Concurrency, Prentice-Hall (1989).
Owicki, S. and Gries, D.: Verifying Properties of Parallel Programs: An Axiomatic Approach, Comm. ACM, Vol. 19, No. 5, pp.279–285 (1976).
Owicki, S. and Gries, D.: An Axiomatic Proof Technique for Parallel Programs I: Acta Inf., Vol. 6, pp.319–340 (1976).
Mizutani, T: An analytical equivalence theory of programs with applications, Ph.D. Thesis, University of Tsukuba (1987).
Mizutani, T., Igarashi, S. and Tsuji, T.: An Analytical Equivalence Theory of Computer Programs, A. Díez, J. Echeverría and A. Ibarra, eds., Structures in Mathematical Theories, Reports of the San Sebastian International Symposium, pp.199–204 (1990).
Pnueli, A. and Harel, E.: Applications of temporal logic to the specification of real time systems, M. Joseph, ed., Proc. Symp. Formal Techn. in Real-Time and Fault-Tolerant Systems, Lecture Notes in Computer Science 331, pp.84–98 (1988).
Shoenfield, J. R.: Mathematical Logic, Addison-Wesley (1967).
Takeuti, G.: Two Applications of Logic to Mathematics, Iwanami Shoten, Publishers and Princeton University Press (1978).
Tomita, K., Tsuji, T. and Igarashi, S.: An Analysis of a Real Time Problem Using v-Conversion and Its Safety Conditions, Transactions of Information Processing Society of Japan, Vol.34, No.5, pp.1099–1106 (In Japanese) (1993).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Tomita, K., Tsuji, T., Igarashi, S. (1994). Analysis of a software/hardware system by tense arithmetic. In: Jones, N.D., Hagiya, M., Sato, M. (eds) Logic, Language and Computation. Lecture Notes in Computer Science, vol 792. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0032401
Download citation
DOI: https://doi.org/10.1007/BFb0032401
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57935-9
Online ISBN: 978-3-540-48391-5
eBook Packages: Springer Book Archive