8 papers
-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 tw…
(Sets of ) Complement Scattered Factors
Duncan Adamson, Pamela Fleischmann, Annika Huch
Starting in the 1970s with the fundamental work of Imre Simon, \emph{scattered factors} (also known as subsequences or scattered subwords) have remained a consistently and heavily…
Word Chain Generators for Prefix Normal Words
Duncan Adamson, Moritz Dudey, Pamela Fleischmann +1
In 2011, Fici and Lipták introduced prefix normal words. A binary word is prefix normal if it has no factor (substring) that contains more occurrences of the letter 1 than the pref…
-Universality of Regular Languages Revisited
Duncan Adamson, Pamela Fleischmann, Annika Huch +2
A subsequence of a word is a word such that , for some set of indices . A word is \e…
Rollercoasters with Plateaus
Duncan Adamson, Pamela Fleischmann, Annika Huch
In this paper we investigate the problem of detecting, counting, and enumerating (generating) all maximum length plateau--rollercoasters appearing as a subsequence of some given…
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…
Enumerating m-Length Walks in Directed Graphs with Constant Delay
Duncan Adamson, Pawel Gawrychowski, Florin Manea
In this paper, we provide a novel enumeration algorithm for the set of all walks of a given length within a directed graph. Our algorithm has worst-case constant delay between outp…
-Universality of Regular Languages
Duncan Adamson, Pamela Fleischmann, Annika Huch +3
A subsequence of a word is a word such that , for some set of indices . A word is…