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 条
[31]   Semi-Heyting Algebras Term-equivalent to Godel Algebras [J].
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
[32]   Residuated lattices arising from equivalence relations on Boolean and Brouwerian algebras [J].
Vetterlein, Thomas .
MATHEMATICAL LOGIC QUARTERLY, 2008, 54 (04) :350-367
[33]   MacNeille transferability and stable classes of Heyting algebras [J].
Guram Bezhanishvili ;
John Harding ;
Julia Ilin ;
Frederik Möllerström Lauridsen .
Algebra universalis, 2018, 79
[34]   Profiniteness and representability of spectra of Heyting algebras [J].
Bezhanishvili, G. ;
Bezhanishvili, N. ;
Moraschini, T. ;
Stronkowski, M. .
ADVANCES IN MATHEMATICS, 2021, 391
[35]   Metric Boolean algebras and constructive measure theory [J].
Coquand, T ;
Palmgren, E .
ARCHIVE FOR MATHEMATICAL LOGIC, 2002, 41 (07) :687-704
[36]   Metric Boolean algebras and constructive measure theory [J].
Thierry Coquand ;
Erik Palmgren .
Archive for Mathematical Logic, 2002, 41 :687-704
[37]   On algebras conditionally rationally equivalent to semilatticies and Boolean algebras [J].
Pinus, AG .
SIBERIAN MATHEMATICAL JOURNAL, 1998, 39 (01) :106-112
[38]   On algebras conditionally rationally equivalent to semilatticies and boolean algebras [J].
A. G. Pinus .
Siberian Mathematical Journal, 1998, 39 :106-112
[39]   An encoding of partial algebras as total algebras [J].
Diaconescu, Razvan .
INFORMATION PROCESSING LETTERS, 2009, 109 (23-24) :1245-1251
[40]   σ-short Boolean algebras [J].
Takahashi, M ;
Yoshinobu, Y .
MATHEMATICAL LOGIC QUARTERLY, 2003, 49 (06) :543-549
12345