Vše

Co hledáte?

Vše
Projekty
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

On the Complexity of Validity Degrees in Łukasiewicz Logic

Identifikátory výsledku

  • Kód výsledku v IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F20%3A00531136" target="_blank" >RIV/67985807:_____/20:00531136 - isvavai.cz</a>

  • Výsledek na webu

    <a href="http://dx.doi.org/10.1007/978-3-030-51466-2_15" target="_blank" >http://dx.doi.org/10.1007/978-3-030-51466-2_15</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.1007/978-3-030-51466-2_15" target="_blank" >10.1007/978-3-030-51466-2_15</a>

Alternativní jazyky

  • Jazyk výsledku

    angličtina

  • Název v původním jazyce

    On the Complexity of Validity Degrees in Łukasiewicz Logic

  • Popis výsledku v původním jazyce

    Lukasiewicz logic is an established formal system of manyvalued logic. Decision problems in both propositional and first-order case have been classified as to their computational complexity or degrees of undecidability. For the propositional fragment, theoremhood and provability from finite theories are coNP complete. This paper extends the range of results by looking at validity degree in propositional Lukasiewicz logic, a natural optimization problem to find the minimal value of a term under a finite theory in a fixed complete semantics interpreting the logic. A classification for this problem is provided using the oracle class FPNP, where it is shown complete under metric reductions.

  • Název v anglickém jazyce

    On the Complexity of Validity Degrees in Łukasiewicz Logic

  • Popis výsledku anglicky

    Lukasiewicz logic is an established formal system of manyvalued logic. Decision problems in both propositional and first-order case have been classified as to their computational complexity or degrees of undecidability. For the propositional fragment, theoremhood and provability from finite theories are coNP complete. This paper extends the range of results by looking at validity degree in propositional Lukasiewicz logic, a natural optimization problem to find the minimal value of a term under a finite theory in a fixed complete semantics interpreting the logic. A classification for this problem is provided using the oracle class FPNP, where it is shown complete under metric reductions.

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/GA18-00113S" target="_blank" >GA18-00113S: Usuzování se stupňovanými vlastnostmi</a><br>

  • Návaznosti

    P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Ostatní

  • Rok uplatnění

    2020

  • 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

    Beyond the Horizon of Computability

  • ISBN

    978-3-030-51465-5

  • ISSN

    0302-9743

  • e-ISSN

  • Počet stran výsledku

    14

  • Strana od-do

    175-188

  • Název nakladatele

    Springer

  • Místo vydání

    Cham

  • Místo konání akce

    Salerno

  • Datum konání akce

    29. 6. 2020

  • Typ akce podle státní příslušnosti

    WRD - Celosvětová akce

  • Kód UT WoS článku