A Set-Theoretic Decision Procedure for Quantifier-Free, Decidable Languages Extended with Restricted Quantifiers

preprint2022arXivOpen access

Abstract

Let LX\mathcal{L}_{\mathcal{X}} be the language of first-order, decidable theory X\mathcal{X}. Consider the language, LRQ(X)\mathcal{L}_{\mathcal{RQ}}(\mathcal{X}), that extends LX\mathcal{L}_{\mathcal{X}} with formulas of the form ∀x∈A:ϕ\forall x \in A: ϕ (restricted universal quantifier, RUQ) and ∃x∈A:ϕ\exists x \in A: ϕ (restricted existential quantifier, REQ), where AA is a finite set and ϕϕ is a formula made of X\mathcal{X}-formulas, RUQ and REQ. That is, LRQ(X)\mathcal{L}_{\mathcal{RQ}}(\mathcal{X}) admits nested restricted quantifiers. In this paper we present a decision procedure for LRQ(X)\mathcal{L}_{\mathcal{RQ}}(\mathcal{X}) based on the decision procedure already defined for the Boolean algebra of finite sets extended with restricted intensional sets (LRIS\mathcal{L}_\mathcal{RIS}). The implementation of the decision procedure as part of the {log}\{log\} (`setlog') tool is also introduced. The usefulness of the approach is shown through a number of examples drawn from several real-world case studies.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.