DROPS

Document

DOI: 10.4230/LIPIcs.FSCD.2025.21

An Expressive Trace Logic for Recursive Programs

Authors: Dilian Gurov and Reiner Hähnle

Published in: LIPIcs, Volume 337, 10th International Conference on Formal Structures for Computation and Deduction (FSCD 2025)

Abstract

We present an expressive logic over trace formulas, based on binary state predicates, chop, and least fixed points, for precise specification of programs with recursive procedures. Both programs and trace formulas are equipped with a direct-style, fully compositional, denotational semantics that on programs coincides with the standard SOS of recursive programs. We design a compositional proof calculus for proving finite-trace program properties, and prove soundness as well as (relative) completeness. We show that each program can be mapped to a semantics-preserving trace formula and, vice versa, each trace formula can be mapped to a canonical program over slightly extended programs, resulting in a Galois connection between programs and formulas. Our results shed light on the correspondence between programming constructs and logical connectives.

Cite as

Dilian Gurov and Reiner Hähnle. An Expressive Trace Logic for Recursive Programs. In 10th International Conference on Formal Structures for Computation and Deduction (FSCD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 337, pp. 21:1-21:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gurov_et_al:LIPIcs.FSCD.2025.21,
  author =	{Gurov, Dilian and H\"{a}hnle, Reiner},
  title =	{{An Expressive Trace Logic for Recursive Programs}},
  booktitle =	{10th International Conference on Formal Structures for Computation and Deduction (FSCD 2025)},
  pages =	{21:1--21:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-374-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{337},
  editor =	{Fern\'{a}ndez, Maribel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2025.21},
  URN =		{urn:nbn:de:0030-drops-236360},
  doi =		{10.4230/LIPIcs.FSCD.2025.21},
  annote =	{Keywords: Denotational semantics, compositional semantics, program specification, compositional verification, fixed point logic, trace logic}
}

Document

DOI: 10.4230/DagRep.12.11.1

Principles of Contract Languages (Dagstuhl Seminar 22451)

Authors: Dilian Gurov, Reiner Hähnle, Marieke Huisman, Giles Reger, and Christian Lidström

Published in: Dagstuhl Reports, Volume 12, Issue 11 (2023)

Abstract

This report documents the program and the outcomes of Dagstuhl Seminar 22451 "Principles of Contract Languages". At the seminar, participants discussed the fundamental aspects of software contracts. Topics included the format and expressiveness of contracts, their use cases in software development and analysis, and contract composition and decomposition.

Cite as

Dilian Gurov, Reiner Hähnle, Marieke Huisman, Giles Reger, and Christian Lidström. Principles of Contract Languages (Dagstuhl Seminar 22451). In Dagstuhl Reports, Volume 12, Issue 11, pp. 1-27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{gurov_et_al:DagRep.12.11.1,
  author =	{Gurov, Dilian and H\"{a}hnle, Reiner and Huisman, Marieke and Reger, Giles and Lidstr\"{o}m, Christian},
  title =	{{Principles of Contract Languages (Dagstuhl Seminar 22451)}},
  pages =	{1--27},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{12},
  number =	{11},
  editor =	{Gurov, Dilian and H\"{a}hnle, Reiner and Huisman, Marieke and Reger, Giles and Lidstr\"{o}m, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.11.1},
  URN =		{urn:nbn:de:0030-drops-178334},
  doi =		{10.4230/DagRep.12.11.1},
  annote =	{Keywords: software contracts, program specifications, software development, program analysis}
}

Search Results

Documents authored by Gurov, Dilian

An Expressive Trace Logic for Recursive Programs

Abstract

Cite as

Principles of Contract Languages (Dagstuhl Seminar 22451)

Abstract

Cite as

Thanks for your feedback!

Could not send message