1 citations · 1 across the 5 of their papers we have counts for
7 papers
Language-Representability: Possibilities and Limitations
Zhidan Feng, Henning Fernau, Pamela Fleischmann +2
The study of word-representability was initiated by the seminal work of Kitaev and Pyatkin in 2008 that has later led to the monograph by Kitaev and Lozin in 2015. In this paper, w…
-word--representable Graphs
Duncan Adamson, Amanita Dietz, Pamela Fleischmann +2
This paper investigates the new notion of -word--repre\-sentable graphs: the nodes of the graph correspond to the letters of the two words and there exists an edge between t…
Towards Settling the Complexity of the Lettericity Problem
Mario Grobler, Nils Morawietz, Silas Cato Sacher
The lettericity of a graph is defined as the smallest size of an alphabet such that there is a word and a decoder $\mathcal{D} \subseteq…
On Languages Describing Large Graph Classes
Henning Fernau, Pamela Fleischmann, Kevin Mann +1
In this work, we introduce a new notion for representing graph classes with formal languages. In contrast to the seminal work by Kitaev and Pyatkin to represent graphs by words, we…
Determining Factorial Speed Fast
Zhidan Feng, Henning Fernau, Pamela Fleischmann +2
The speed of a graph class measures how many labeled graphs on vertices one can find in . This graph class complexity function is explicitly provided on graphc…
Arithmetic Circuits with Division
Silas Cato Sacher
We study the computational complexity of the membership problem for arithmetic circuits over natural numbers with division. We consider different subsets of the operations {interse…