2026-08-05T04:16:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18603 2024-03-12T12:01:35Z ddc:004 open_access

On the Finite Variable-Occurrence Fragment of the Calculus of Relations with Bounded Dot-Dagger Alternation Nakamura, Yoshiki Relation algebra First-order logic Decidable fragment Monoid We introduce the k-variable-occurrence fragment, which is the set of terms having at most k occurrences of variables. We give a sufficient condition for the decidability of the equational theory of the k-variable-occurrence fragment using the finiteness of a monoid. As a case study, we prove that for Tarski’s calculus of relations with bounded dot-dagger alternation (an analogy of quantifier alternation in first-order logic), the equational theory of the k-variable-occurrence fragment is decidable for each k. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yoshiki Nakamura 2023 Is Part Of LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2023.69 urn:nbn:de:0030-drops-186030 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.69 eng https://creativecommons.org/licenses/by/4.0/legalcode