2 citations · 10 across the 16 of their papers we have counts for
18 papers
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 -complete, and, more strongly, computably isomorphic to true sec…
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…
Extending Action Logic with Omega Iteration
Tikhon Pshenitsyn
We present a proof system that extends action logic by omega iteration, which is viewed as infinitary multiplicative conjunction. We prove cut admissibility and establish complexit…
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…
Complexity of decision problems for hyperedge replacement grammars
Tikhon Pshenitsyn
This paper investigates complexity of various decision problems for hyperedge replacement grammars, starting with the uniform membership problem. It turns out that the complexity o…
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…
Bonding Grammars
Tikhon Pshenitsyn
We introduce bonding grammars, a graph grammar formalism developed to model DNA computation by means of graph transformations. It is a modification of fusion grammars introduced by…
Hyperarithmetical Complexity of Infinitary Action Logic with Multiplexing
Tikhon Pshenitsyn
In 2023, Kuznetsov and Speranski introduced infinitary action logic with multiplexing and proved that the derivability problem for it lies between the $ω…
Expressive Power of Hypergraph Lambek Grammars
Tikhon Pshenitsyn
Hypergraph Lambek grammars (HL-grammars) is a novel logical approach to generating graph languages based on the hypergraph Lambek calculus. In this paper, we establish a precise re…
On Decidability and Expressive Power of Fusion Grammars
Tikhon Pshenitsyn
We study algorithmic complexity and expressive power of fusion grammars, a novel formalism introduced in [Kreowski, Kuske, and Lye 2017], which extends hyperedge replacement gramma…
Multimodality in the Hypergraph Lambek Calculus
Tikhon Pshenitsyn
The multimodal Lambek calculus is an extension of the Lambek calculus that includes several product operations (some of them being commutative or/and associative), unary modalities…
From Double Pushout Grammars to Hypergraph Lambek Grammars With and Without Exponential Modality
Tikhon Pshenitsyn
We study how to relate well-known hypergraph grammars based on the double pushout (DPO) approach and grammars over the hypergraph Lambek calculus HL (called HL-grammars). It turns…
Grammars over the Lambek Calculus with Permutation: Recognizing Power and Connection to Branching Vector Addition Systems with States
Tikhon Pshenitsyn
In (Van Benthem, 1991) it is proved that all permutation closures of context-free languages can be generated by grammars over the Lambek calculus with the permutation rule (LP-gram…
Grammars Based on a Logic of Hypergraph Languages
Tikhon Pshenitsyn
The hyperedge replacement grammar (HRG) formalism is a natural and well-known generalization of context-free grammars. HRGs inherit a number of properties of context-free grammars,…
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…
Introduction to a Hypergraph Logic Unifying Different Variants of the Lambek Calculus
Tikhon Pshenitsyn
In this paper hypergraph Lambek calculus () is presented. This formalism aims to generalize the Lambek calculus () to hypergraphs as hyperedge replacement…
Weak Greibach Normal Form for Hyperedge Replacement Grammars
Tikhon Pshenitsyn
It is known that hyperedge replacement grammars are similar to string context-free grammars in the sense of definitions and properties. Therefore, we expect that there is a general…
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…