Infinitary action logic with multiplexing

Studia Logica. 2023. Vol. 111. No. 2. P. 251–280.

Кузнецов С. Л., Сперанский С. О.

Infinitary action logic can be naturally expanded by adding exponential and subexponential modalities from linear logic. In this article we shall develop infinitary action logic with a subexponential that allows multiplexing (instead of contraction). Both non-commutative and commutative versions of this logic will be considered, presented as infinitary sequent calculi. We shall prove cut admissibility for these calculi, and estimate the complexity of the corresponding derivability problems: in both cases it will turn out to be between complete first-order arithmetic and the $\omega^{\omega}$ level of the hyperarithmetical hierarchy. Here the complexity upper bound is much lower than that for the system with a subexponential that allows contraction. The complexity lower bound in turn is much higher than that for infinitary action logic.

Ключевые слова: complexity, Lambek calculus, infinitary action logic, multiplexing, closure ordinal