Rules with parameters in modal logic II

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F20%3A00524632" target="_blank" >RIV/67985840:_____/20:00524632 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1016/j.apal.2020.102829" target="_blank" >https://doi.org/10.1016/j.apal.2020.102829</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.apal.2020.102829" target="_blank" >10.1016/j.apal.2020.102829</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Rules with parameters in modal logic II

Popis výsledku v původním jazyce

We analyze the computational complexity of admissibility and unifiability with parameters in transitive modal logics. The class of cluster-extensible (clx) logics was introduced in the first part of this series of papers [8]. We completely classify the complexity of unifiability or inadmissibility in any clx logic as being complete for one of Σ2 exp, NEXP, coNEXP, PSPACE, or Π2 p. In addition to the main case where arbitrary parameters are allowed, we consider restricted problems with the number of parameters bounded by a constant, and the parameter-free case. Our upper bounds are specific to clx logics, but we also include similar results for logics of bounded depth and width. In contrast, our lower bounds are very general: they apply each to a class of all transitive logics whose frames allow occurrence of certain finite subframes. We also discuss the baseline problem of complexity of derivability: it is coNP-complete or PSPACE-complete for each clx logic. In particular, we prove PSPACE-hardness of derivability for a broad class of transitive logics that includes all logics with the disjunction property.

Název v anglickém jazyce

Rules with parameters in modal logic II

Popis výsledku anglicky

We analyze the computational complexity of admissibility and unifiability with parameters in transitive modal logics. The class of cluster-extensible (clx) logics was introduced in the first part of this series of papers [8]. We completely classify the complexity of unifiability or inadmissibility in any clx logic as being complete for one of Σ2 exp, NEXP, coNEXP, PSPACE, or Π2 p. In addition to the main case where arbitrary parameters are allowed, we consider restricted problems with the number of parameters bounded by a constant, and the parameter-free case. Our upper bounds are specific to clx logics, but we also include similar results for logics of bounded depth and width. In contrast, our lower bounds are very general: they apply each to a class of all transitive logics whose frames allow occurrence of certain finite subframes. We also discuss the baseline problem of complexity of derivability: it is coNP-complete or PSPACE-complete for each clx logic. In particular, we prove PSPACE-hardness of derivability for a broad class of transitive logics that includes all logics with the disjunction property.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/GA19-05497S" target="_blank" >GA19-05497S: Složitost matematických důkazů a struktur</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

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ů

Název periodika

Annals of Pure and Applied Logic

ISSN

0168-0072

e-ISSN

—

Svazek periodika

171

Číslo periodika v rámci svazku

10

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

59

Strana od-do

102829

Kód UT WoS článku

000568991900008

EID výsledku v databázi Scopus

2-s2.0-85084806006