Tikhon Pshenitsyn

activity

20202026

most citedIntroduction to a Hypergraph Logic Unifying Different Variants of the Lambek Calculus

2 citations · 10 across the 16 of their papers we have counts for

collaborators

Showing math.LOShow all

8 papers · 1 filter

math.LO2026

Exact Complexity of the Satisfiability Problem for Strategy Logic

Tikhon Pshenitsyn

We show that the satisfiability problem for Strategy Logic introduced by Mogavero, Murano, and Vardi is $Π_{\infty}^{1}$ -complete, and, more strongly, computably isomorphic to true sec…

math.LO2026

Wider systems for linear logic with fixed points: proof theory and complexity

Anupam Das, Tikhon Pshenitsyn

We investigate infinitary wellfounded systems for linear logic with fixed points, with transfinite branching rules indexed by some closure ordinal $α$ for fixed points. Our main re…

math.LO2025

First-Order Intuitionistic Linear Logic and Hypergraph Languages

Tikhon Pshenitsyn

The Lambek calculus is a substructural logic known to be closely related to the formal language theory: on the one hand, it is used for generating formal languages by means of cate…

math.LO2024

Reasoning from hypotheses in *-continuous action lattices

Stepan L. Kuznetsov, Tikhon Pshenitsyn, Stanislav O. Speranski

The class of all $*$ -continuous Kleene algebras, whose description includes an infinitary condition on the iteration operator, plays an important role in computer science. The c…

math.LO2023

Hyperarithmetical Complexity of Infinitary Action Logic with Multiplexing

Tikhon Pshenitsyn

In 2023, Kuznetsov and Speranski introduced infinitary action logic with multiplexing $!^{m} \nabla ACT_{ω}$ and proved that the derivability problem for it lies between the $ω…

math.LO2021

Cyclic Shift in the Lambek Calculus

Tikhon Pshenitsyn

We enrich the Lambek calculus with the cyclic shift operation, which is expected to model the closure operator of formal languages with respect to cyclic shifts. We introduce a Gen…

math.LO2021★ 2 cited

Introduction to a Hypergraph Logic Unifying Different Variants of the Lambek Calculus

Tikhon Pshenitsyn

In this paper hypergraph Lambek calculus ( $HL$ ) is presented. This formalism aims to generalize the Lambek calculus ( $L$ ) to hypergraphs as hyperedge replacement…

math.LO2020★ 1 cited

Hypergraph Lambek Calculus

Tikhon Pshenitsyn

It is known that context-free grammars can be extended to generating graphs resulting in graph grammars; one of such fundamental approaches is hyperedge replacement grammars. On th…