DROPS

Document

DOI: 10.4230/LIPIcs.CSL.2026.14

Satisfiability in Łukasiewicz Logic and Its Unbounded Relative

Authors: Zuzana Haniková and Filip Jankovec

Published in: LIPIcs, Volume 363, 34th EACSL Annual Conference on Computer Science Logic (CSL 2026)

Abstract

Unbounded Łukasiewicz logic is a substructural logic that combines features of infinite-valued Łukasiewicz logic with those of abelian logic. The logic is finitely strongly complete w.r.t. the additive 𝓁-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 Łukasiewicz logic. The result is obtained by reducing the problem to the existential theory of the MV-algebra on the reals, the standard semantics of Łukasiewicz 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.

Cite as

Zuzana Haniková and Filip Jankovec. Satisfiability in Łukasiewicz Logic and Its Unbounded Relative. In 34th EACSL Annual Conference on Computer Science Logic (CSL 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 363, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hanikova_et_al:LIPIcs.CSL.2026.14,
  author =	{Hanikov\'{a}, Zuzana and Jankovec, Filip},
  title =	{{Satisfiability in {\L}ukasiewicz Logic and Its Unbounded Relative}},
  booktitle =	{34th EACSL Annual Conference on Computer Science Logic (CSL 2026)},
  pages =	{14:1--14:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-411-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{363},
  editor =	{Guerrini, Stefano and K\"{o}nig, Barbara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2026.14},
  URN =		{urn:nbn:de:0030-drops-254380},
  doi =		{10.4230/LIPIcs.CSL.2026.14},
  annote =	{Keywords: unbounded {\L}ukasiewicz Logic, {\L}ukasiewicz Logic, Abelian Logic, existential theory, computational complexity, NP-completeness}
}

Search Results

Documents authored by Jankovec, Filip

Satisfiability in Łukasiewicz Logic and Its Unbounded Relative

Abstract

Cite as

Thanks for your feedback!

Could not send message