<link rel="stylesheet" href="styles.f3b1fba60ec7970c.css">

Artículo:
Proving Correctness of Problem Reductions Using Dafny

Cargando...
Miniatura

Editor

Sistedes

Publicado en

Actas de las XXIV Jornadas de Programación y Lenguajes (PROLE 2025)

Licencia Creative Commons

Excepto donde se indique lo contrario, la licencia de este ítem se describe como CC BY-NC-ND 4.0

Resumen

Dafny is a programming language that allows users to check the correctness of their code. This requires a formal specification of what a program is expected to do, and a mechanism to prove that the actual behavior of the program satisfies the specification. The way Dafny proves correctness is by invoking the SMT solver called Z3. This means that Dafny can be used just like any other theorem prover, no matter if they are interactive like Isabelle or Coq, or non-interactive like Vampire. Our intention is to explore how effective Dafny is at proving the correctness of reductions between two decision problems. A reduction typically involves transforming one problem into another in such a way that an algorithm solving the second problem can be used to solve the original one. We are particularly interested in determining whether Dafny is suitable for proving the correctness of such reductions.

Descripción

Acerca de Hermo, Montserrat

Citación

Hermo, M., Alonso, A., Barrena, M.: Proving Correctness of Problem Reductions Using Dafny. In: Pino, E. (ed.) Actas de las XXIV Jornadas de Programación y Lenguajes (PROLE 2025). Sistedes (2025). https://hdl.handle.net/11705/PROLE/2025/3