5 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…
Tight Bounds for the Number of Absent Subsequences
Duncan Adamson, Pamela Fleischmann, Annika Huch +3
A {\em subsequence} of a word is a word that can be obtained by deleting some letters from while maintaining the relative order of the remaining letters, e.g., $\mathtt…
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 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…
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…