Satisfiability in Lukasiewicz logic and its unbounded relative

Result code in 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>

Result on the web

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

Result language

angličtina

Original language name

Satisfiability in Lukasiewicz logic and its unbounded relative

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/EH23_025%2F0008711" target="_blank" >EH23_025/0008711: Knowledge in the Age of Distrust</a><br>

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2026

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

34th EACSL Annual Conference on Computer Science Logic (CSL 2026) Proceedings

ISBN

978-3-95977-411-6

ISSN

—

e-ISSN

—

Number of pages

18

Pages from-to

14

Publisher name

Schloss Dagstuhl, Leibniz-Zentrum für Informatik

Place of publication

Dagstuhl

Event location

Paris

Event date

Feb 24, 2026

Type of event by nationality

EUR - Evropská akce

UT code for WoS article

—