Complexity of Boolean algebras
From MaRDI portal
Publication:1137036
DOI10.1016/0304-3975(80)90048-1zbMath0428.03036OpenAlexW2083251422MaRDI QIDQ1137036
Publication date: 1980
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(80)90048-1
Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Boolean algebras (Boolean rings) (06E99)
Related Items (20)
Alternating tree automata ⋮ Existentially closed semilattices ⋮ On the complexity of Boolean unification ⋮ Negative Boolean constraints ⋮ The complexity of linear problems in fields ⋮ A characterization of pseudofinite MV-algebras ⋮ Deciding Boolean algebra with Presburger arithmetic ⋮ Dominoes and the complexity of subclasses of logical theories ⋮ A canonical form of vector machines ⋮ On decidable varieties of Heyting algebras ⋮ Tree-size bounded alternation ⋮ Classifying the computational complexity of problems ⋮ A uniform method for proving lower bounds on the computational complexity of logical theories ⋮ Definability with bounded number of bound variables ⋮ Dynamic algebras: Examples, constructions, applications ⋮ Complexity of logical theories involving coprimality ⋮ The Evaluation and the Computational Complexity of Datalog Queries of Boolean Constraint Databases ⋮ What is nominalistic mereology? ⋮ Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories ⋮ Simple sentences that are hard to decide
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Model theory.
- The polynomial-time hierarchy
- On the computational power of pushdown automata
- An application of games to the completeness problem for formalized theories
- A Decision Procedure for the First Order Theory of Real Addition with Order
- Rudimentary Predicates and Relative Computation
- The complexity of theorem-proving procedures
This page was built for publication: Complexity of Boolean algebras