Skip to main content
SpringerLink
Log in

A faithful embedding of parallel computations in star-finite models

  • Published:
Studia Logica Aims and scope Submit manuscript

Abstract

The purpose of this paper is to show that there exist star-finite tree-structured sets in which the computations of parallel programs can be faithfully embedded, and that the theory of star-finite sets and relations therefore provides a new tool for the analysis of non-deterministic computations.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Reference

  1. L. Csirmaz, Programs and program verification in a general setting, Theoret. Comp. Sci. 16 (1981), pp. 199–210.

    Google Scholar 

  2. L. Csirmaz, Nonstandard semantics in program verification, Hungarian Academy of Sciences, 1984.

  3. N. J. Cutland, Computability, Cambridge 1980.

  4. E. J. Farkas, A type structure for parallel programs, Ph.D. Thesis, Concordia University, Montreal 1985.

    Google Scholar 

  5. E. J. Farkas and M. E. Szabo, On ihn progarms-as-formulas interpretationion of parallel programs in Peano arithmetic, Annals of Pure and Applied Logic 37 (1988), pp. 111–127.

    Google Scholar 

  6. E. J. Farkas and M. E. Szabo, Stochastic analysis of loop programs, 1986. To appear.

  7. S. Hart, M. Sharir and A. Pnueli, Termination of probabilistic concurrent programs, ACM Trans, on Programming Languages and Systems 5 (1983), pp. 356–380.

    Google Scholar 

  8. M. M. Richter, Ideale Punkte, Monaden, und Nichtstandard-Methoden, Vieweg, 1982.

  9. M. M. Richter and M. E. Szabo, Towards a nonstandard analysis oj programs, in: A. E. Hurd, ed., Nonstandard Analysis — Recent Developments, Lecture Notes in Mathematics 983, Springer-Verlag, 1983.

  10. M. M. Richtr and M. E. Szabo. Nonstandard computation theory. in: J. Demetrovics. G. Katona, and A. Salomaa, eds., Algebra, Combinatorics, and Logic in Computer Science, Colloquia Mathematica Soc. J. Bolyai 42, North-Holland, Amsterdam, 1983.

    Google Scholar 

  11. M. E. Szabo, On some arithmetically expressible properties of programs, in: G. Mirkowska and H Rasiowa. eds. Mathematical Problems in Computer Science, Banach Center Publications 21. Warsaw. 1986. pp.383 392.

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics and Statistics, McGill University, 805 Sherbrooke St. West, H3A 2K6, Montreal, Quebec, Canada

    E. J. Farkas

Authors
  1. E. J. Farkas
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This research was carried out while the author held a Postdoctoral Fellowship from the Natural Sciences and Engineering Research Council of Canada. The author also gratefully acknowledges the support of the Centre inter-universitaire en études catégoriques de Montréal.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Farkas, E.J. A faithful embedding of parallel computations in star-finite models. Stud Logica 47, 203–212 (1988). https://doi.org/10.1007/BF00370551

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00370551

Keywords

Search

Navigation