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

DOI10.1016/J.TCS.2013.05.012zbMATH Open1296.03020OpenAlexW1976154566MaRDI QIDQ391322FDOQ391322

C. 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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Logic in computer science (03B70) Structure theory of Boolean algebras (06E05) Structure and representation theory of distributive lattices (06D05) Partial algebras (08A55) Applications of universal algebra in computer science (08A70) Heyting algebras (lattice-theoretic aspects) (06D20)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Elements of finite model theory.
• Lectures on the Curry-Howard isomorphism
• The finite embeddability property for residuated lattices, pocrims and BCK-algebras.
• On closed elements in closure algebras
• The decision problem for some classes of sentences without quantifiers
• Recursive Unsolvability of a problem of Thue
• On the structure of hoops
• The word and generator problems for lattices
• Intuitionistic propositional logic is polynomial-space complete
• Polynomial Time Uniform Word Problems
• Embeddability and the word problem
• 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

Cited In (6)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q391322)