6 papers
Uniform Membership for Hyperedge Replacement Grammars and Related Decision Problems
Tikhon Pshenitsyn
This paper investigates complexity of the uniform membership problem for hyperedge replacement grammars in comparison with other mildly context-sensitive grammar formalisms. It tur…
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 r…
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…
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…
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…