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
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
Boolean algebradistributive latticeHeyting algebrauniversal theorycomplexity of satisfiabilitypartial algebrapartial structure
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
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