Complexity assessments for decidable fragments of set theory. II: A taxonomy for `small' languages involving membership
From MaRDI portal
Publication:2215960
DOI10.1016/j.tcs.2020.08.023zbMath1498.03113OpenAlexW3080392153MaRDI QIDQ2215960
Pietro Maugeri, Domenico Cantone, Eugenio Giovanni Omodeo
Publication date: 15 December 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2020.08.023
Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) Mechanization of proofs and logical operations (03B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Axiomatics of classical set theory and its fragments (03E30)
Related Items
Complexity assessments for decidable fragments of Set Theory. III: Testers for crucial, polynomial-maximal decidable Boolean languages, Complexity Assessments for Decidable Fragments of Set Theory. I: A Taxonomy for the Boolean Case*
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Interval propagation to reason about sets: Definition and implementation of a practical language
- Decision procedures for elementary sublanguages of set theory: X. Multilevel syllogistic extended by the singleton and powerset operators
- Embedding Boolean expressions into logic programming
- The automation of syllogistic. II: Optimization and complexity issues
- Formative processes with applications to the decision problem in set theory. I: Powerset and singleton operators
- Formative processes with applications to the decision problem in set theory. II. Powerset and singleton operators, finiteness predicate
- Solving quantifier-free first-order constraints over finite sets and binary relations
- A new algorithm for optimal 2-constraint satisfaction and its implications
- {log}: A language for programming in logic with finite sets
- Set unification
- Decision procedures for elementary sublanguages of set theory. I. Multi-level syllogistic and some extensions
- An Introduction to the Technique of Formative Processes in Set Theory
- Computational Logic and Set Theory
- On Sets and Graphs
