Tree Rewriting Calculi for Strictly Positive Logics
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.
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}
}
EUVIMED