4 papers
An Analysis of Decision Problems for Relational Pattern Languages under Various Constraints
Klaus Jansen, Dirk Nowotka, Lis Pirotton +2
Patterns are words with terminals and variables. The language of a pattern is the set of words obtained by uniformly substituting all variables with words that contain only termina…
Word-Representable Graphs and Locality of Words
Philipp Böll, Pamela Fleischmann, Annika Huch +4
In this work, we investigate the relationship between -repre\-sentable graphs and graphs representable by -local words. In particular, we show that every graph representable…
The Equivalence Problem of E-Pattern Languages with Regular Constraints is Undecidable
Dirk Nowotka, Max Wiedenhöft
Patterns are words with terminals and variables. The language of a pattern is the set of words obtained by uniformly substituting all variables with words that contain only termina…
The Equivalence Problem of E-Pattern Languages with Length Constraints is Undecidable
Dirk Nowotka, Max Wiedenhöft
Patterns are words with terminals and variables. The language of a pattern is the set of words obtained by uniformly substituting all variables with words that contain only termina…