English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We investigate the non-elementary computational complexity of a family ofsubstructural logics without contraction. With the aid of the techniquepioneered by Lazi\'c and Schmitz (2015), we show that the deducibility problemfor full Lambek calculus with exchange and weakening($\mathbf{FL}_{\mathbf{ew}}$) is not in Elementary (i.e., the class of decisionproblems that can be decided in time bounded by an elementary recursivefunction), but is in PR (i.e., the class of decision problems that can bedecided in time bounded by a primitive recursive function). More precisely, weshow that this problem is complete for Tower, which is a non-elementarycomplexity class forming a part of the fast-growing complexity hierarchyintroduced by Schmitz (2016). The same complexity result holds even fordeducibility in BCK-logic, i.e., the implicational fragment of$\mathbf{FL}_{\mathbf{ew}}$. We furthermore show the Tower-completeness of theprovability problem for elementary affine logic, which was proved to bedecidable by Dal Lago and Martini (2004).

Tower-Complete Problems in Contraction-Free Substructural Logics