Automata-Theoretic Semantics of Idealized Algol with Passive Expressions

Research output: Contribution to conference (unpublished)Paperpeer-review

Abstract

Passive expressions in Algol-like languages represent computations that read the state but do not modify it. The need for such read-only computations arises in programming logics as well as in concurrent programming. It is also a central facet in Reynolds's Syntactic Control of Interference. Despite its importance and essentially basic character, capturing the notion of passivity in semantic models has proved to be difficult. In this paper, we provide a new model of passive expressions using an automata-theoretic framework recently proposed by the author. The central idea is that the store of a program is viewed as an abstract form of an automaton, with a representation of its states as well as state transitions. The framework allows us to combine the strengths of conventional state-based models and the more recent event-based models to synthesize new "automata-based" models. Once this basic framework is set up, relational parametricity does the job of identifying passive computations.
Original languageEnglish
Pages325-348
Number of pages24
DOIs
Publication statusPublished - 4 Nov 2013
Event29th Conference on Mathematical Foundations of Programming Semantics (MFPS XXIX) - New Orelans, United States
Duration: 23 Jun 201325 Jun 2013

Conference

Conference29th Conference on Mathematical Foundations of Programming Semantics (MFPS XXIX)
Country/TerritoryUnited States
CityNew Orelans
Period23/06/1325/06/13

Keywords

  • Idealized Algol
  • Relational parametricity
  • Functor categories
  • Reflexive graphs
  • Algebraic automata theory

ASJC Scopus subject areas

  • Computer Science(all)
  • Computational Theory and Mathematics
  • Theoretical Computer Science

Fingerprint

Dive into the research topics of 'Automata-Theoretic Semantics of Idealized Algol with Passive Expressions'. Together they form a unique fingerprint.
  • An Automata-Theoretic Model of Idealized Algol

    Reddy, U. & Dunphy, B. P., 2012, Automata, Languages, and Programming: 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part II. Czumaj, A., Mehlhorn, K., Pitts, A. & Wattenhofer, R. (eds.). Springer, p. 337-350 (Lecture Notes in Computer Science; vol. 7392).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    1 Citation (Scopus)
  • An Automata-Theoretic Model of Objects

    Reddy, U. & Dunphy, BP., 23 Oct 2011. 15 p.

    Research output: Contribution to conference (unpublished)Paper

    Open Access
    File
  • Parametric limits

    Dunphy, BP. & Reddy, U., 1 Jan 2004, p. 242-253. 12 p.

    Research output: Contribution to conference (unpublished)Paperpeer-review

    Open Access
    File
    16 Citations (Scopus)
    97 Downloads (Pure)

Cite this