Computing Witnesses Using the SCAN Algorithm
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918475846385664 |
|---|---|
| author | Achammer, Fabian Hetzl, Stefan Schmidt, Renate A. |
| author_facet | Achammer, Fabian Hetzl, Stefan Schmidt, Renate A. |
| contents | Second-order quantifier elimination is the problem of finding, given a formula with second-order quantifiers, a logically equivalent first-order formula. While such formulas are not computable in general, there are practical algorithms and subclasses with applications throughout computational logic. One of the most prominent algorithms for second-order quantifier elimination is the saturation-based SCAN algorithm. In this paper we show how the SCAN algorithm on clause sets can be extended to solve a more general problem: namely, finding a witness for the second-order quantifiers that results in a logically equivalent first-order formula. In addition, we provide a prototype implementation of the proposed method. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_27939 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Computing Witnesses Using the SCAN Algorithm Achammer, Fabian Hetzl, Stefan Schmidt, Renate A. Logic in Computer Science Second-order quantifier elimination is the problem of finding, given a formula with second-order quantifiers, a logically equivalent first-order formula. While such formulas are not computable in general, there are practical algorithms and subclasses with applications throughout computational logic. One of the most prominent algorithms for second-order quantifier elimination is the saturation-based SCAN algorithm. In this paper we show how the SCAN algorithm on clause sets can be extended to solve a more general problem: namely, finding a witness for the second-order quantifiers that results in a logically equivalent first-order formula. In addition, we provide a prototype implementation of the proposed method. |
| title | Computing Witnesses Using the SCAN Algorithm |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2604.27939 |