Complexity assessments for decidable fragments of set theory. I: A taxonomy for the Boolean case

DOI10.3233/FI-2021-2050zbMATH Open1498.03112OpenAlexW3177543793MaRDI QIDQ5158658FDOQ5158658

Authors: Domenico Cantone, Andrea de Domenico, Pietro Maugeri, Eugenio Omodeo 

Publication date: 25 October 2021

Published in: Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3233/fi-2021-2050

Recommendations

• Complexity assessments for decidable fragments of set theory. II: A taxonomy for `small' languages involving membership
• Decision procedures for elementary sublanguages of set theory: X. Multilevel syllogistic extended by the singleton and powerset operators
• Decision procedures for elementary sublanguages of set theory. VI. Multi-level syllogistic extended by the powerset operator
• Techniques of computable set theory with applications to proof verification
• Formative processes with applications to the decision problem in set theory. II. Powerset and singleton operators, finiteness predicate

zbMATH Keywords

NP-completenesssatisfiability problemproof verificationexpressibilitycomputable set theoryBoolean set theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Decidability of theories and sets of sentences (03B25) Mechanization of proofs and logical operations (03B35) Axiomatics of classical set theory and its fragments (03E30)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Embedding Boolean expressions into logic programming
• {log}: A language for programming in logic with finite sets
• Set graphs. III: Proof pearl: Claw-free graphs mirrored into transitive hereditarily finite sets
• Title not available (Why is that?)
• Computational logic and set theory. Applying formalized logic to analysis. Foreword by Martin Davis
• Title not available (Why is that?)
• THE COMPLEXITY OF SATISFIABILITY FOR FRAGMENTS OF CTL AND CTL⋆
• Complexity results for classes of quantificational formulas
• Solving quantifier-free first-order constraints over finite sets and binary relations
• Decision procedures for elementary sublanguages of set theory. I. Multi-level syllogistic and some extensions
• Title not available (Why is that?)
• Decision procedures for elementary sublanguages of set theory. II. Formulas involving restricted quantifiers, together with ordinal, integer, map, and domain notions
• Title not available (Why is that?)
• Decision procedures for elementary sublanguages of set theory: X. Multilevel syllogistic extended by the singleton and powerset operators
• Title not available (Why is that?)
• Formative processes with applications to the decision problem in set theory. I: Powerset and singleton operators
• The automation of syllogistic. II: Optimization and complexity issues
• Title not available (Why is that?)
• Model checking for fragments of the interval temporal logic HS at the low levels of the polynomial time hierarchy
• Which fragments of the interval temporal logic HS are tractable in model checking?
• Title not available (Why is that?)
• On sets and graphs. Perspectives on logic and combinatorics
• Set unification
• Complexity assessments for decidable fragments of set theory. II: A taxonomy for `small' languages involving membership
• Formative processes with applications to the decision problem in set theory. II. Powerset and singleton operators, finiteness predicate
• An introduction to the technique of formative processes in set theory
• A uniform approach to constraint-solving for lists, multisets, compact lists, and sets

Cited In (3)

• Complexity assessments for decidable fragments of set theory. II: A taxonomy for `small' languages involving membership
• On the convexity of a fragment of pure set theory with applications within a Nelson-Oppen framework
• Complexity assessments for decidable fragments of Set Theory. III: Testers for crucial, polynomial-maximal decidable Boolean languages

This page was built for publication: Complexity assessments for decidable fragments of set theory. I: A taxonomy for the Boolean case

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5158658)