2 citations · 10 across the 16 of their papers we have counts for
7 papers · 1 filter
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…
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…
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…
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,…
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…