frantrucco

Room 411

Nijenborgh 9

Groningen, 9747 AG

I am a formal methods researcher in my last year of my PhD in Computer Science at the University of Groningen. The main focus of my PhD has been styding metalogical properties about Propositional Dynamic Logic. I contributed to resolving a forty-year-old open problem and earned a Best Student Paper Award at the international conference TABLEAUX 2025. I also have some industry experience formally verifying browser security mechanisms at TU Wien and proving compiler correctness at the Max Planck Institute for Security and Privacy for Cryptographic Protocols. I am interested in formal analysis techniques to prove correctness of cryptographic protocols, distributed algorithms, and hardware designs.

selected publications

TABLEAUX
Interpolation for Converse Propositional Dynamic Logic

Johannes Kloibhofer, Francisco Trucco Dalmas, and Yde Venema

In Automated Reasoning with Analytic Tableaux and Related Methods (TABLEAUX 2025), 2025

Best Student Paper Abs Bib

Best Student Paper Award

Converse PDL is the extension of propositional dynamic logic with a converse operation on programs. Our main result states that Converse PDL enjoys the (local) Craig Interpolation Property, with respect to both atomic programs and propositional variables. As a corollary we establish the Beth Definability Property for the logic. Our interpolation proof is based on an adaptation of Maehara’s proof-theoretic method. For this purpose we introduce a sound and complete cyclic sequent system for this logic. This calculus features an analytic cut rule and uses a focus mechanism for recognising successful cycles.
@inproceedings{kloibhofer2025interpolation, author = {Kloibhofer, Johannes and Trucco Dalmas, Francisco and Venema, Yde}, title = {Interpolation for Converse Propositional Dynamic Logic}, booktitle = {Automated Reasoning with Analytic Tableaux and Related Methods (TABLEAUX 2025)}, year = {2025}, publisher = {Springer}, url = {https://link.springer.com/chapter/10.1007/978-3-032-06085-3_14}, }
arXiv
Propositional Dynamic Logic has Craig Interpolation: a tableau-based proof

Manfred Borzechowski, Malvin Gattinger, Helle Hvid Hansen, and 3 more authors

2025

arXiv preprint arXiv:2503.13276

Abs arXiv Bib

We show that Propositional Dynamic Logic (PDL) has the Craig Interpolation Property. This question has been open for many years. Three proof attempts were published, but later criticized in the literature or retracted. Our proof is based on the main ideas from Borzechowski (1988). We define a cyclic tableau system for PDL with a loading mechanism to recognize successful repeats. For this system, we show soundness and completeness via a game. To show interpolation, we modify Maehara’s method to work for tableaux with repeats: we first define pre-interpolants at each node, and then use a quasi-tableau to define interpolants for clusters (strongly connected components). In different terms, our method solves the fixpoint equations that characterize the desired interpolants, and the method ensures that the solutions to these equations can be expressed within PDL. The proof is constructive and we show how to compute interpolants. We also make available a Haskell implementation of the proof system that provides interpolants. Lastly, we mention ongoing work to formally verify this proof in the interactive theorem prover Lean, and several questions for future work.
@unpublished{borzechowski2025pdlcraig, author = {Borzechowski, Manfred and Gattinger, Malvin and Hvid Hansen, Helle and Ramanayake, Revantha and Trucco Dalmas, Francisco and Venema, Yde}, title = {Propositional Dynamic Logic has Craig Interpolation: a tableau-based proof}, year = {2025}, note = {arXiv preprint arXiv:2503.13276}, url = {https://arxiv.org/abs/2503.13276}, }