Satisfiability in Lukasiewicz logic and its unbounded relative
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F26%3A00643950" target="_blank" >RIV/67985807:_____/26:00643950 - isvavai.cz</a>
Výsledek na webu
<a href="https://doi.org/10.4230/LIPIcs.CSL.2026.14" target="_blank" >https://doi.org/10.4230/LIPIcs.CSL.2026.14</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.CSL.2026.14" target="_blank" >10.4230/LIPIcs.CSL.2026.14</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Satisfiability in Lukasiewicz logic and its unbounded relative
Popis výsledku v původním jazyce
Unbounded Lukasiewicz logic is a substructural logic that combines features of infinite-valued Lukasiewicz logic with those of abelian logic. The logic is finitely strongly complete w.r.t. the additive l-group on the reals expanded with a distinguished element -1. We show that the existential theory of this structure is NP-complete. This provides a complexity upper bound for the set of theorems and the finite consequence relation of unbounded Lukasiewicz logic. The result is obtained by reducing the problem to the existential theory of the MV-algebra on the reals, the standard semantics of Lukasiewicz logic. This provides a new connection between both logics. The result entails a translation of the existential theory of the standard MV-algebra into itself.
Název v anglickém jazyce
Satisfiability in Lukasiewicz logic and its unbounded relative
Popis výsledku anglicky
Unbounded Lukasiewicz logic is a substructural logic that combines features of infinite-valued Lukasiewicz logic with those of abelian logic. The logic is finitely strongly complete w.r.t. the additive l-group on the reals expanded with a distinguished element -1. We show that the existential theory of this structure is NP-complete. This provides a complexity upper bound for the set of theorems and the finite consequence relation of unbounded Lukasiewicz logic. The result is obtained by reducing the problem to the existential theory of the MV-algebra on the reals, the standard semantics of Lukasiewicz logic. This provides a new connection between both logics. The result entails a translation of the existential theory of the standard MV-algebra into itself.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
<a href="/cs/project/EH23_025%2F0008711" target="_blank" >EH23_025/0008711: Vědění ve věku nedůvěry</a><br>
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2026
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
34th EACSL Annual Conference on Computer Science Logic (CSL 2026) Proceedings
ISBN
978-3-95977-411-6
ISSN
—
e-ISSN
—
Počet stran výsledku
18
Strana od-do
14
Název nakladatele
Schloss Dagstuhl, Leibniz-Zentrum für Informatik
Místo vydání
Dagstuhl
Místo konání akce
Paris
Datum konání akce
24. 2. 2026
Typ akce podle státní příslušnosti
EUR - Evropská akce
Kód UT WoS článku
—