EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

The Complex(ity) Landscape of Checking Infinite Descent

Liron Cohen, Adham Jabarin, Andrei Popescu, Reuben N. S. Rowe

Proceedings of the ACM on Programming Languages · 02.01.2024 · 8 (POPL) · 1352-1384

DOI: 10.1145/3632888 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Programming Languages, online erschienen am 05.01.2024. Verfasst von Liron Cohen und 3 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 53 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Royal Society.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Cyclic proof systems, in which induction is managed implicitly, are a promising approach to automatic verification. The soundness of cyclic proof graphs is ensured by checking them against a trace-based Infinite Descent property. Although the problem of checking Infinite Descent is known to be PSPACE-complete, this leaves much room for variation in practice. Indeed, a number of different approaches are employed across the various cyclic proof systems described in the literature. In this paper, we study criteria for Infinite Descent in an abstract, logic-independent setting. We look at criteria based on Büchi automata encodings and relational abstractions, and determine their parameterized time complexities in terms of natural dimensions of cyclic proofs: the numbers of vertices of the proof-tree graphs, and the vertex width —an upper bound on the number of components (e.g., formulas) of a sequent that can be simultaneously tracked for descent. We identify novel algorithms that improve upon the parameterised complexity of the existing algorithms. We implement the studied criteria and compare their performance on various benchmarks.

Förderung

  • Royal Society

Zitieren

APA

Cohen, L., Jabarin, A., Popescu, A., & Rowe, R. N. S. (2024). The Complex(ity) Landscape of Checking Infinite Descent. Proceedings of the ACM on Programming Languages, 8(POPL), 1352-1384. https://doi.org/10.1145/3632888

Vancouver

Cohen L, Jabarin A, Popescu A, Rowe RNS. The Complex(ity) Landscape of Checking Infinite Descent. Proceedings of the ACM on Programming Languages. 2024;8(POPL):1352-1384. doi:10.1145/3632888

BibTeX
@article{Cohen2024,
  author = {Cohen, Liron and Jabarin, Adham and Popescu, Andrei and Rowe, Reuben N. S.},
  title = {The Complex(ity) Landscape of Checking Infinite Descent},
  journal = {Proceedings of the ACM on Programming Languages},
  year = {2024},
  volume = {8},
  number = {POPL},
  pages = {1352--1384},
  doi = {10.1145/3632888}
}
Kostenlos starten →