Complexity assessments for decidable fragments of Set Theory. III: Testers for crucial, polynomial-maximal decidable Boolean languages

DOI10.1016/j.tcs.2023.113786OpenAlexW4323350838MaRDI QIDQ2697538

Pietro Maugeri, Domenico Cantone, Eugenio Giovanni Omodeo

Publication date: 12 April 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2023.113786

zbMATH Keywords

NP-completenessexpressibilitysatisfiability problemproof verificationcomputable set theoryBoolean set theory

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Embedding Boolean expressions into logic programming
• Complexity, convexity and combinations of theories
• The automation of syllogistic. II: Optimization and complexity issues
• Complexity assessments for decidable fragments of set theory. II: A taxonomy for `small' languages involving membership
• Solving quantifier-free first-order constraints over finite sets and binary relations
• Set unification
• Deciding Combinations of Theories
• Decision procedures for elementary sublanguages of set theory IX. Unsolvability of the decision problem for a restricted subclass of the Δ0-formulas in set theory
• Fast Decision Procedures Based on Congruence Closure
• Simplification by Cooperating Decision Procedures
• Decision procedures for elementary sublanguages of set theory. I. Multi-level syllogistic and some extensions
• Complexity Assessments for Decidable Fragments of Set Theory. I: A Taxonomy for the Boolean Case*
• Computational Logic and Set Theory
• A uniform approach to constraint-solving for lists, multisets, compact lists, and sets

This page was built for publication: Complexity assessments for decidable fragments of Set Theory. III: Testers for crucial, polynomial-maximal decidable Boolean languages