Substructural logics

Prelegent(ci)

Paweł Urzyczyn

Afiliacja

MIMUW

Termin

21 kwietnia 2023 12:15

Pokój

p. 5820

Seminarium

Semantyka, Logika I Weryfikacja Oraz Wiele Ich Ciekawych Aplikacji

---

Wiadomo, że logiki BCI i BCK są NP-zupełne. Ale jak się dobrze
postawi pytanie o wnioskowanie w BCK (BCI), to odpowiedź jest
całkiem inna i może być nawet akermańska.

It is known that BCI and BCK logics are NP-complete. But if the
question of deducibility in BCK (BCI) is properly stated then the
answer is quite different, even Ackermannian.

References: H. Tanaka, CSL 2023 and R. Lazić, S. Schmitz, ACM ToCL 2015.

---