Substructural logics

Speaker(s)

Paweł Urzyczyn

Affiliation

MIMUW

Date

April 21, 2023, 12:15 p.m.

Room

room 5820

Seminar

Seminar Semantics, Logic, Verification and its Applications

---

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.

---