Number of the records: 1  

Term Satisfiability in FLew-Algebras

  1. 1.
    0439177 - ÚI 2017 RIV NL eng J - Journal Article
    Haniková, Zuzana - Savický, Petr
    Term Satisfiability in FLew-Algebras.
    Theoretical Computer Science. Roč. 631, 6 June (2016), s. 1-15. ISSN 0304-3975. E-ISSN 1879-2294
    R&D Projects: GA ČR GBP202/12/G061
    Institutional support: RVO:67985807
    Keywords : substructural logic * FLew-algebra * MV-algebra * satisfiability * computational complexity
    OECD category: Pure mathematics
    Impact factor: 0.698, year: 2016

    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.
    Permanent Link:

    a0439177.pdf8496.2 KBPublisher’s postprintrequire
Number of the records: 1