Počet záznamů: 1  

New Complexity Results for Lukasiewicz Logic

  1. 1.
    SYSNO ASEP0491990
    Druh ASEPJ - Článek v odborném periodiku
    Zařazení RIVJ - Článek v odborném periodiku
    Poddruh JČlánek ve WOS
    NázevNew Complexity Results for Lukasiewicz Logic
    Tvůrce(i) Bofill, M. (ES)
    Manya, F. (ES)
    Vidal, Amanda (UIVT-O) RID, SAI, ORCID
    Villaret, M. (ES)
    Zdroj.dok.Soft Computing. - : Springer - ISSN 1432-7643
    Roč. 23, č. 7 (2019), s. 2187-2197
    Poč.str.11 s.
    Jazyk dok.eng - angličtina
    Země vyd.DE - Německo
    Klíč. slovaLukasiewicz logics ; Clausal forms ; Complexity ; Instance generator
    Vědní obor RIVIN - Informatika
    Obor OECDComputer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
    CEPGA17-04630S GA ČR - Grantová agentura ČR
    Způsob publikováníOpen access
    Institucionální podporaUIVT-O - RVO:67985807
    UT WOS000461580400006
    EID SCOPUS85049926337
    DOI10.1007/s00500-018-3365-9
    AnotaceOne aspect that has been poorly studied in multiple-valued logics, and in particular in Lukasiewicz logic, is the generation of instances of varying difficulty for evaluating, comparing and improving satisfiability solvers. With the ultimate goal of finding challenging benchmarks for Lukasiewicz satisfiability solvers, we start by defining a natural and intuitive class of clausal forms (simple L-clausal forms) and studying their complexity. Since we prove that the satisfiability problem of simple L-clausal forms can be solved in linear time, we then define two new classes of clausal forms (L-clausal forms and restricted L-clausal forms) that truly exploit the non-lattice operations of Lukasiewicz logic and whose satisfiability problems are NP-complete when clauses have at least three literals, and admit linear-time algorithms when clauses have at most two literals. We also define an efficient satisfiability preserving translation of Lukasiewicz logic formulas into L-clausal forms. Finally, we describe a random generator of L-clausal forms and report on an empirical investigation in which we identify an easy-hard-easy pattern and a phase transition phenomenon for L-clausal forms.
    PracovištěÚstav informatiky
    KontaktTereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800
    Rok sběru2020
    Elektronická adresahttp://hdl.handle.net/11104/0285586
Počet záznamů: 1  

  Tyto stránky využívají soubory cookies, které usnadňují jejich prohlížení. Další informace o tom jak používáme cookies.