Complexity of Boolean algebras

DOI10.1016/0304-3975(80)90048-1zbMath0428.03036OpenAlexW2083251422MaRDI QIDQ1137036

Dexter Kozen

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

zbMATH Keywords

decision procedurealternating Turing machinescomputable setsfirst order theory of Boolean algebras

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Boolean algebras (Boolean rings) (06E99)

Related Items

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

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Complexity of Boolean algebras