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 条
12345