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

DOI10.1016/J.TCS.2013.05.012zbMath1296.03020OpenAlexW1976154566MaRDI 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

Analysis of algorithms and problem complexity (68Q25) Logic in computer science (03B70) Applications of universal algebra in computer science (08A70) Heyting algebras (lattice-theoretic aspects) (06D20) Structure and representation theory of distributive lattices (06D05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Structure theory of Boolean algebras (06E05) Partial algebras (08A55)

Related Items (6)

Term satisfiability in \(\mathrm{FL}_{\mathrm{ew}}\)-algebras ⋮ Polynomial space hardness without disjunction property ⋮ Complexity of the universal theory of residuated ordered groupoids ⋮ 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

This page was built for publication: Partial algebras and complexity of satisfiability and universal theory for distributive lattices, Boolean algebras and Heyting algebras