Short proofs without interference
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918124478005248 |
|---|---|
| author | Rebola-Pardo, Adrian |
| author_facet | Rebola-Pardo, Adrian |
| contents | Interference is a phenomenon on proof systems for SAT solving that is both counter-intuitive and bothersome when developing proof-logging techniques. However, all existing proof systems that can produce short proofs for all inprocessing techniques deployed by SAT present this feature. Based on insights from propositional dynamic logic, we propose a framework that eliminates interference while preserving the same expressive power of interference-based proofs. Furthermore, we propose a first building blocks towards RUP-like decision procedures for our dynamic logic-based frameworks, which are essential to developing effective proof checking methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_09851 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Short proofs without interference Rebola-Pardo, Adrian Logic in Computer Science Interference is a phenomenon on proof systems for SAT solving that is both counter-intuitive and bothersome when developing proof-logging techniques. However, all existing proof systems that can produce short proofs for all inprocessing techniques deployed by SAT present this feature. Based on insights from propositional dynamic logic, we propose a framework that eliminates interference while preserving the same expressive power of interference-based proofs. Furthermore, we propose a first building blocks towards RUP-like decision procedures for our dynamic logic-based frameworks, which are essential to developing effective proof checking methods. |
| title | Short proofs without interference |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2508.09851 |