Interpolation for Converse PDL
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911158847406080 |
|---|---|
| author | Kloibhofer, Johannes Dalmas, Valentina Trucco Venema, Yde |
| author_facet | Kloibhofer, Johannes Dalmas, Valentina Trucco Venema, Yde |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_21485 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Interpolation for Converse PDL Kloibhofer, Johannes Dalmas, Valentina Trucco Venema, Yde Logic in Computer Science 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. |
| title | Interpolation for Converse PDL |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2508.21485 |