Volume

Dagstuhl Seminar Proceedings, Volume 10351

Publication Details

  • published at: 2010-11-04
  • Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Access Numbers

Documents

No documents found matching your filter selection.
Document
DOI: 10.4230/DagSemProc.10351.1
10351 Abstracts Collection – Modelling, Controlling and Reasoning About State

Authors: Amal Ahmed, Nick Benton, Lars Birkedal, and Martin Hofmann

Abstract
From 29 August 2010 to 3 September 2010, the Dagstuhl Seminar 10351 ``Modelling, Controlling and Reasoning About State '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. Links to extended abstracts or full papers are provided, if available.
Cite as

Amal Ahmed, Nick Benton, Lars Birkedal, and Martin Hofmann. 10351 Abstracts Collection – Modelling, Controlling and Reasoning About State. In Modelling, Controlling and Reasoning About State. Dagstuhl Seminar Proceedings, Volume 10351, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{ahmed_et_al:DagSemProc.10351.1,
  author =	{Ahmed, Amal and Benton, Nick and Birkedal, Lars and Hofmann, Martin},
  title =	{{10351 Abstracts Collection – Modelling, Controlling and Reasoning About State}},
  booktitle =	{Modelling, Controlling and Reasoning About State},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10351},
  editor =	{Amal Ahmed and Nick Benton and Lars Birkedal and Martin Hofmann},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10351.1},
  URN =		{urn:nbn:de:0030-drops-28116},
  doi =		{10.4230/DagSemProc.10351.1},
  annote =	{Keywords: Mutable State, Program Logics, Semantics, Type Systems, Verification}
}
Document
DOI: 10.4230/DagSemProc.10351.2
10351 Executive Summary – Modelling, Controlling and Reasoning About State

Authors: Amal Ahmed, Nick Benton, Lars Birkedal, and Martin Hofmann

Abstract
From 29 August 2010 to 3 September 2010, the Dagstuhl Seminar 10351 ``Modelling, Controlling and Reasoning About State '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. 44 researchers, with interests and expertise in many different aspects of modelling and reasoning about mutable state, met to present their current work and discuss ongoing projects and open problems. This executive summary provides a general overview of the goals of the seminar and of the topics discussed.
Cite as

Amal Ahmed, Nick Benton, Lars Birkedal, and Martin Hofmann. 10351 Executive Summary – Modelling, Controlling and Reasoning About State. In Modelling, Controlling and Reasoning About State. Dagstuhl Seminar Proceedings, Volume 10351, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{ahmed_et_al:DagSemProc.10351.2,
  author =	{Ahmed, Amal and Benton, Nick and Birkedal, Lars and Hofmann, Martin},
  title =	{{10351 Executive Summary – Modelling, Controlling and Reasoning About State}},
  booktitle =	{Modelling, Controlling and Reasoning About State},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10351},
  editor =	{Amal Ahmed and Nick Benton and Lars Birkedal and Martin Hofmann},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10351.2},
  URN =		{urn:nbn:de:0030-drops-28108},
  doi =		{10.4230/DagSemProc.10351.2},
  annote =	{Keywords: Mutable State, Program Logics, Semantics, Type Systems, Verification}
}
Document
DOI: 10.4230/DagSemProc.10351.3
A Theory of Termination via Indirection

Authors: Robert Dockins and Aquinas Hobor

Abstract
Step-indexed models provide approximations to a class of domain equations and can prove type safety, partial correctness, and program equivalence; however, a common misconception is that they are inapplicable to liveness problems. We disprove this by applying step-indexing to develop the first Hoare logic of total correctness for a language with function pointers and semantic assertions. In fact, from a liveness perspective, our logic is stronger: we verify explicit time resource bounds. We apply our logic to examples containing nontrivial "higher-order" uses of function pointers and we prove soundness with respect to a standard operational semantics. Our core technique is very compact and may be applicable to other liveness problems. Our results are machine checked in Coq.
Cite as

Robert Dockins and Aquinas Hobor. A Theory of Termination via Indirection. In Modelling, Controlling and Reasoning About State. Dagstuhl Seminar Proceedings, Volume 10351, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{dockins_et_al:DagSemProc.10351.3,
  author =	{Dockins, Robert and Hobor, Aquinas},
  title =	{{A Theory of Termination via Indirection}},
  booktitle =	{Modelling, Controlling and Reasoning About State},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10351},
  editor =	{Amal Ahmed and Nick Benton and Lars Birkedal and Martin Hofmann},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10351.3},
  URN =		{urn:nbn:de:0030-drops-28050},
  doi =		{10.4230/DagSemProc.10351.3},
  annote =	{Keywords: Step-indexed Models, Termination}
}
Document
DOI: 10.4230/DagSemProc.10351.4
Limitations of Applicative Bisimulation (Preliminary Report)

Authors: Vasileios Koutavas, Paul Blain Levy, and Eijiro Sumii

Abstract
We present a series of examples that illuminate an important aspect of the semantics of higher-order functions with local state. Namely that certain behaviour of such functions can only be observed by pro- viding them with arguments that contain the functions themselves. This provides evidence for the necessity of complex conditions for functions in modern semantics for state, such as logical relations and Kripke-like bisimulations, where related functions are applied to related arguments (that may contain the functions). It also suggests that simpler semantics, such as those based on applicative bisimulations where functions are ap- plied to identical arguments, would not scale to higher-order languages with local state.
Cite as

Vasileios Koutavas, Paul Blain Levy, and Eijiro Sumii. Limitations of Applicative Bisimulation (Preliminary Report). In Modelling, Controlling and Reasoning About State. Dagstuhl Seminar Proceedings, Volume 10351, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{koutavas_et_al:DagSemProc.10351.4,
  author =	{Koutavas, Vasileios and Levy, Paul Blain and Sumii, Eijiro},
  title =	{{Limitations of Applicative Bisimulation (Preliminary Report)}},
  booktitle =	{Modelling, Controlling and Reasoning About State},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10351},
  editor =	{Amal Ahmed and Nick Benton and Lars Birkedal and Martin Hofmann},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10351.4},
  URN =		{urn:nbn:de:0030-drops-28074},
  doi =		{10.4230/DagSemProc.10351.4},
  annote =	{Keywords: Imperative languages, higher-order functions, local state}
}
Document
DOI: 10.4230/DagSemProc.10351.5
Program Equivalence with Names

Authors: Nikos Tzevelekos

Abstract
The nu-calculus of Pitts and Stark was introduced as a paradigmatic functional language with a very basic local-state effect: references of unit type. These were called names, and the motto of the new language went as follows: "Names are created with local scope, can be tested for equality, and are passed around via function application, but that is all." Because of this limited framework, the hope was that fully abstract models and complete proof techniques could be obtained. However, it was soon realised that the behaviour of nu-calculus programs is quite intricate, and program equivalence in particular is surprisingly difficult to capture. Here we shall focus on the following "hard" equivalence. new x,y in f. (fx=fy) == f. true We shall examine attempts and proofs of the above, explain the advantages and disadvantages of the proof methods and discuss why program equivalence in this simple language remains to date a mystery.
Cite as

Nikos Tzevelekos. Program Equivalence with Names. In Modelling, Controlling and Reasoning About State. Dagstuhl Seminar Proceedings, Volume 10351, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{tzevelekos:DagSemProc.10351.5,
  author =	{Tzevelekos, Nikos},
  title =	{{Program Equivalence with Names}},
  booktitle =	{Modelling, Controlling and Reasoning About State},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10351},
  editor =	{Amal Ahmed and Nick Benton and Lars Birkedal and Martin Hofmann},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10351.5},
  URN =		{urn:nbn:de:0030-drops-28092},
  doi =		{10.4230/DagSemProc.10351.5},
  annote =	{Keywords: Nu-calculus, Local State, Logical Relations, Game Semantics, Environmental Bisimulations}
}
Document
DOI: 10.4230/DagSemProc.10351.6
Step-Indexed Biorthogonality: a Tutorial Example

Authors: Andrew M. Pitts

Abstract
The purpose of this note is to illustrate the use of step-indexing combined with biorthogonality to construct syntactical logical relations. It walks through the details of a syntactically simple, yet non-trivial example: a proof of the "CIU Theorem'' for contextual equivalence in the untyped call-by-value $lambda$-calculus with recursively defined functions.
Cite as

Andrew M. Pitts. Step-Indexed Biorthogonality: a Tutorial Example. In Modelling, Controlling and Reasoning About State. Dagstuhl Seminar Proceedings, Volume 10351, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{pitts:DagSemProc.10351.6,
  author =	{Pitts, Andrew M.},
  title =	{{Step-Indexed Biorthogonality: a Tutorial Example}},
  booktitle =	{Modelling, Controlling and Reasoning About State},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10351},
  editor =	{Amal Ahmed and Nick Benton and Lars Birkedal and Martin Hofmann},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10351.6},
  URN =		{urn:nbn:de:0030-drops-28067},
  doi =		{10.4230/DagSemProc.10351.6},
  annote =	{Keywords: Biorthogonality, logical relations, operational semantics, step-indexing}
}
Document
DOI: 10.4230/DagSemProc.10351.7
Step-Indexing: The Good, the Bad and the Ugly

Authors: Nick Benton and Chung-Kil Hur

Abstract
Over the last decade, step-indices have been widely used for the construction of operationally-based logical relations in the presence of various kinds of recursion. We first give an argument that step-indices, or something like them, seem to be required for defining realizability relations between high-level source languages and low-level targets, in the case that the low-level allows egregiously intensional operations such as reflection or comparison of code pointers. We then show how, much to our annoyance, step-indices also seem to prevent us from exploiting such operations as aggressively as we would like in proving program transformations.
Cite as

Nick Benton and Chung-Kil Hur. Step-Indexing: The Good, the Bad and the Ugly. In Modelling, Controlling and Reasoning About State. Dagstuhl Seminar Proceedings, Volume 10351, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{benton_et_al:DagSemProc.10351.7,
  author =	{Benton, Nick and Hur, Chung-Kil},
  title =	{{Step-Indexing: The Good, the Bad and the Ugly}},
  booktitle =	{Modelling, Controlling and Reasoning About State},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10351},
  editor =	{Amal Ahmed and Nick Benton and Lars Birkedal and Martin Hofmann},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10351.7},
  URN =		{urn:nbn:de:0030-drops-28085},
  doi =		{10.4230/DagSemProc.10351.7},
  annote =	{Keywords: Step-Indexing, Logical Relations, Low-Level Languages, Compiler Correctness}
}

Filters

  • Authors
  • A
  • Ahmed, Amal
  • B
  • Benton, Nick
  • Birkedal, Lars
  • D
  • Dockins, Robert
  • H
  • Hobor, Aquinas
  • Hofmann, Martin
  • Hur, Chung-Kil
  • K
  • Koutavas, Vasileios
  • L
  • Levy, Paul Blain
  • P
  • Pitts, Andrew M.
  • S
  • Sumii, Eijiro
  • T
  • Tzevelekos, Nikos

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact