Number of the records: 1

Term Satisfiability in FLew-Algebras

SYSNO ASEP	0439177
Document Type	J - Journal Article
R&D Document Type	Journal Article
Subsidiary J	Článek ve WOS
Title	Term Satisfiability in FLew-Algebras
Author(s)	Haniková, Zuzana (UIVT-O)_{SAI, RID, ORCID} Savický, Petr (UIVT-O)_{SAI, RID, ORCID}
Source Title	Theoretical Computer Science. - : Elsevier - ISSN 0304-3975 Roč. 631, 6 June (2016), s. 1-15
Number of pages	15 s.
Language	eng - English
Country	NL - Netherlands
Keywords	substructural logic ; FLew-algebra ; MV-algebra ; satisfiability ; computational complexity
Subject RIV	BA - General Mathematics
OECD category	Pure mathematics
R&D Projects	GBP202/12/G061 GA ČR - Czech Science Foundation (CSF)
Institutional support	UIVT-O - RVO:67985807
UT WOS	000377839900001
EID SCOPUS	84977943182
DOI	10.1016/j.tcs.2016.03.009
Annotation	FLew-algebras form the algebraic semantics of the full Lambek calculus with exchange and weakening. We investigate two relations, called satisfiability and positive satisfiability, between FLew-terms and FLew-algebras. For each FLew-algebra, the sets of its satisfiable and positively satisfiable terms can be viewed as fragments of its existential theory; we identify and investigate the complements as fragments of its universal theory. We offer characterizations of those algebras that (positively) satisfy just those terms that are satisfiable in the two-element Boolean algebra providing its semantics to classical propositional logic. In case of positive satisfiability, these algebras are just the nontrivial weakly contractive algebras. In case of satisfiability, we give a characterization by means of another property of the algebra, the existence of a two-element congruence. Further, we argue that (positive) satisfiability problems in FLew-algebras are computationally hard. Some previous results in the area of term satisfiabilty in MV-algebras or BL-algebras, are thus brought to a common footing with, e.g., known facts on satisfiability in Heyting algebras.
Workplace	Institute of Computer Science
Contact	Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800
Year of Publishing	2017

Number of the records: 1