Partial algebras and complexity of satisfiability and universal theory for distributive lattices, Boolean algebras and Heyting algebras

DOI10.1016/j.tcs.2013.05.012zbMath1296.03020MaRDI QIDQ391322

Clint J. van Alten

Publication date: 10 January 2014

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

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

zbMATH Keywords

Boolean algebradistributive latticeHeyting algebrauniversal theorycomplexity of satisfiabilitypartial algebrapartial structure

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

03B70: Logic in computer science

08A70: Applications of universal algebra in computer science

06D20: Heyting algebras (lattice-theoretic aspects)

06D05: Structure and representation theory of distributive lattices

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

06E05: Structure theory of Boolean algebras

08A55: Partial algebras

Related Items

Complexity of the universal theory of residuated ordered groupoids, Term satisfiability in \(\mathrm{FL}_{\mathrm{ew}}\)-algebras, Computational complexity for bounded distributive lattices with negation, Complexity of the universal theory of modal algebras, Complexity of the universal theory of bounded residuated distributive lattice-ordered groupoids

Cites Work

• Unnamed Item
• Unnamed Item
• Elements of finite model theory.
• Lectures on the Curry-Howard isomorphism
• The word and generator problems for lattices
• Intuitionistic propositional logic is polynomial-space complete
• The finite embeddability property for residuated lattices, pocrims and BCK-algebras.
• On the structure of hoops
• On closed elements in closure algebras
• Polynomial Time Uniform Word Problems
• Embeddability and the word problem
• Recursive Unsolvability of a problem of Thue
• On the finite embeddability property for residuated ordered groupoids
• Some Connections between Residual Finiteness, Finite Embeddability and the Word Problem
• The Word Problem for Abstract Algebras
• Embeddability and the Word Problem
• The decision problem for some classes of sentences without quantifiers