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

被引：5
作者：
van Alten, C. J. [1 ]
机构：
[1] Univ Witwatersrand, Sch Comp Sci, ZA-2050 Johannesburg, South Africa
来源：
THEORETICAL COMPUTER SCIENCE | 2013年 / 501卷
关键词：
Partial algebra; Partial structure; Lattice; Distributive lattice; Boolean algebra; Heyting algebra; Satisfiability; Universal theory; FINITE EMBEDDABILITY PROPERTY; WORD;
D O I：
10.1016/j.tcs.2013.05.012
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Characterizations are given for the classes of partial subalgebras of distributive lattices, boolean algebras and Heyting algebras. Thereby, complexity results are obtained for the satisfiability of quantifier-free first-order sentences in these classes. Satisfiability is NP-complete for distributive lattices and boolean algebras, and for Heyting algebras is PSPACE-complete. Consequently, the universal theory of distributive lattices and of boolean algebras is co-NP-complete and the universal theory of Heyting algebras is PSPACE-complete. (C) 2013 Elsevier B.V. All rights reserved.
引用
收藏
页码：82 / 92
页数：11
相关论文
共 50 条
  • [21] MacNeille transferability and stable classes of Heyting algebras
    Bezhanishvili, Guram
    Harding, John
    Ilin, Julia
    Lauridsen, Frederik Mollerstrom
    ALGEBRA UNIVERSALIS, 2018, 79 (03)
  • [22] PUTTING BOUNDED INVOLUTIVE LATTICES, DE MORGAN ALGEBRAS, ORTHOLATTICES AND BOOLEAN ALGEBRAS ON THE "MAP"
    Iorgulescu, Afrodita
    Kinyon, Michael
    JOURNAL OF APPLIED LOGICS-IFCOLOG JOURNAL OF LOGICS AND THEIR APPLICATIONS, 2021, 8 (05): : 1169 - 1213
  • [23] Distributive congruence lattices of congruence-permutable algebras
    Ruzicka, Pavel
    Tuma, Jiri
    Wehrung, Friedrich
    JOURNAL OF ALGEBRA, 2007, 311 (01) : 96 - 116
  • [24] MV and Heyting effect algebras
    Foulis, DJ
    FOUNDATIONS OF PHYSICS, 2000, 30 (10) : 1687 - 1706
  • [25] Endomorphisms of complete heyting algebras
    A. Pultr
    J. Sichler
    Semigroup Forum, 1997, 54 : 364 - 374
  • [26] MV and Heyting Effect Algebras
    D. J. Foulis
    Foundations of Physics, 2000, 30 : 1687 - 1706
  • [27] On the Representation of the Lattices of the Algebraic Sets of the Universal Algebras
    Pinus, A. G.
    BULLETIN OF IRKUTSK STATE UNIVERSITY-SERIES MATHEMATICS, 2019, 29 : 98 - 106
  • [28] Generalizations of the correspondence between Boolean algebras and Boolean rings to orthomodular lattices
    Länger, H
    TATRA MOUNTAINS MATHEMATICAL PUBLICATIONS, VOL 15, 1998: QUANTUM STRUCTURES II, 1998, : 97 - 105
  • [29] Semi-Heyting Algebras Term-equivalent to Godel Algebras
    Abad, Manuel
    Manuel Cornejo, Juan
    Diaz Varela, Jose Patricio
    ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2013, 30 (02): : 625 - 642
  • [30] Strengthening Effect Algebras in a Logical Perspective: Heyting-Wajsberg Algebras
    Martinvaldo Konig
    International Journal of Theoretical Physics, 2014, 53 : 3409 - 3422
12345