EUVIMEDEUVIMED entdecken
Crossref

Tree Rewriting Calculi for Strictly Positive Logics

Sofía Santiago-Fernández, David Fernandez-Duque, Joost J. Joosten

ACM Transactions on Computational Logic · 02.11.2026

DOI: 10.1145/3821565 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Computational Logic, online erschienen am 02.11.2026. Verfasst von Sofía Santiago-Fernández und 2 weiteren Autor:innen. Die Arbeit nennt 33 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study strictly positive logics in the language \(\cal{L}^{+}\) , which constructs formulas from \(\top\) , propositional variables, conjunction, and diamond modalities. We begin with the base system \(\bf K^{+}\) , the strictly positive fragment of polymodal \(\bf K\) , and examine its extensions obtained by adding axioms such as monotonicity, transitivity, and the hierarchy-sensitive interaction axiom \((\sf J)\) , which governs the interplay between modalities of different strengths. The strongest of these systems is the Reflection Calculus ( \(\bf RC\) ), which corresponds to the strictly positive fragment of polymodal \(\bf GLP\) . Our main contribution is a formulation of these logics as tree rewriting systems, establishing both adequacy and completeness through a correspondence between \(\cal{L}^{+}\) formulas and inductively defined modal trees. We also provide a normalization of the rewriting process, which has exponential complexity when axiom \((\sf J)\) is absent; otherwise we provide a double-exponential bound. By introducing tree rewriting calculi as practical provability tools for strictly positive logics, we aim to deepen their proof-theoretic analysis and computational applications.

Zitieren

APA

Santiago-Fernández, S., Fernandez-Duque, D., & Joosten, J. J. (2026). Tree Rewriting Calculi for Strictly Positive Logics. ACM Transactions on Computational Logic. https://doi.org/10.1145/3821565

Vancouver

Santiago-Fernández S, Fernandez-Duque D, Joosten JJ. Tree Rewriting Calculi for Strictly Positive Logics. ACM Transactions on Computational Logic. 2026. doi:10.1145/3821565

BibTeX
@article{SantiagoFernndez2026,
  author = {Santiago-Fernández, Sofía and Fernandez-Duque, David and Joosten, Joost J.},
  title = {Tree Rewriting Calculi for Strictly Positive Logics},
  journal = {ACM Transactions on Computational Logic},
  year = {2026},
  doi = {10.1145/3821565}
}
Kostenlos starten →