Search

In 2017 Day et al. introduced the notion of locality as a structural complexity-measure for patterns in the field of pattern matching established by Angluin in 1980. In 2019 Casel et al. showed that determining the locality of an arbitrary pattern is NP-complete. Inspired by hierarchical clustering, we extend the notion to coloured graphs, i.e., given a coloured graph determine an enumeration of the colours such that colouring the graph stepwise according to the enumeration leads to as few clusters as possible. Next to first theoretical results on graph classes, we propose a priority search algorithm to compute the $k$-locality of a graph. The algorithm is optimal in the number of marking prefix expansions, and is faster by orders of magnitude than an exhaustive search. Finally, we perform a case study on a DBLP subgraph to demonstrate the potential of $k$-locality for knowledge discovery.

In this paper we investigate the problem of detecting, counting, and enumerating (generating) all maximum length plateau-$k$-rollercoasters appearing as a subsequence of some given word (sequence, string), while allowing for plateaus. We define a plateau-$k$-rollercoaster as a word consisting of an alternating sequence of (weakly) increasing and decreasing \emph{runs}, with each run containing at least $k$ \emph{distinct} elements, allowing the run to contain multiple copies of the same symbol consecutively. This differs from previous work, where runs within rollercoasters have been defined only as sequences of distinct values. Here, we are concerned with rollercoasters of \emph{maximum} length embedded in a given word $w$, that is, the longest rollercoasters that are a subsequence of $w$. We present algorithms allowing us to determine the longest plateau-$k$-roller\-coasters appearing as a subsequence in any given word $w$ of length $n$ over an alphabet of size $\sigma$ in $O(n \sigma k)$ time, to count the number of plateau-$k$-rollercoasters in $w$ of maximum length in $O(n \sigma k)$ time, and to output all of them with $O(n)$ delay after $O(n \sigma k)$ preprocessing. Furthermore, we present an algorithm to determine the longest common plateau-$k$-rollercoaster within a set of words in $O(N k \sigma)$ where $N$ is the product of all word lengths within the set.

A scattered factor of a word $w$ is a word $u$ that can be obtained by deleting arbitary letters from $w$ and keep the order of the remaining. Barker et al. introduced the notion of $k$-universality, calling a word $k$-universal, if it contains all possible words of length $k$ over a given alphabet $\Sigma$ as a scattered factor. Kosche et al. introduced the notion of absent scattered factors to categorise the words not being scattered factors of a given word. In this paper, we investigate tight bounds on the possible number of absent scattered factors of a given length $k$ (also strictly longer than the shortest absent scattered factors) among all words with the same universality extending the results of Kosche et al. Specifically, given a length $k$ and universality index $\iota$, we characterize $\iota$-universal words with both the maximal and minimal number of absent scattered factors of length $k$. For the lower bound, we provide the exact number in a closed form. For the upper bound, we offer efficient algorithms to compute the number based on the constructed words. Moreover, by combining old results, we present an enumeration with constant delay of the set of scattered factors of a fixed length in time $O(|\Sigma||w|)$.

A subsequence of a word $w$ is a word $u$ such that $u = w[i_1] w[i_2] \dots w[i_{k}]$, for some set of indices $1 \leq i_1 < i_2 < \dots < i_k \leq \lvert w\rvert$. A word $w$ is $k$-subsequence universal over an alphabet $\Sigma$ if every word in $\Sigma^k$ appears in $w$ as a subsequence. In this paper, we study the intersection between the set of $k$-subsequence universal words over some alphabet $\Sigma$ and regular languages over $\Sigma$. We call a regular language $L$ \emph{$k$-$\exists$-subsequence universal} if there exists a $k$-subsequence universal word in $L$, and \emph{$k$-$\forall$-subsequence universal} if every word of $L$ is $k$-subsequence universal. We give algorithms solving the problems of deciding if a given regular language, represented by a finite automaton recognising it, is \emph{$k$-$\exists$-subsequence universal} and, respectively, if it is \emph{$k$-$\forall$-subsequence universal}, for a given $k$. The algorithms are FPT w.r.t.~the size of the input alphabet, and their run-time does not depend on $k$; they run in polynomial time in the number $n$ of states of the input automaton when the size of the input alphabet is $O(\log n)$. Moreover, we show that the problem of deciding if a given regular language is \emph{$k$-$\exists$-subsequence universal} is NP-complete, when the language is over a large alphabet. Further, we provide algorithms for counting the number of $k$-subsequence universal words (paths) accepted by a given deterministic (respectively, nondeterministic) finite automaton, and ranking an input word (path) within the set of $k$-subsequence universal words accepted by a given finite automaton.

In 1991 H\'ebrard introduced a factorization of words that turned out to be a powerful tool for the investigation of a word's scattered factors (also known as (scattered) subwords or subsequences). Based on this, first Karandikar and Schnoebelen introduced the notion of $k$-richness and later on Barker et al. the notion of $k$-universality. In 2022 Fleischmann et al. presented a generalization of the arch factorization by intersecting the arch factorization of a word and its reverse. While the authors merely used this factorization for the investigation of shortest absent scattered factors, in this work we investigate this new $\alpha$-$\beta$-factorization as such. We characterize the famous Simon congruence of $k$-universal words in terms of $1$-universal words. Moreover, we apply these results to binary words. In this special case, we obtain a full characterization of the classes and calculate the index of the congruence. Lastly, we start investigating the ternary case, present a full list of possibilities for $\alpha\beta\alpha$-factors, and characterize their congruence.

Determining the index of the Simon congruence is a long outstanding open problem. Two words $u$ and $v$ are called Simon congruent if they have the same set of scattered factors, which are parts of the word in the correct order but not necessarily consecutive, e.g., $\mathtt{oath}$ is a scattered factor of $\mathtt{logarithm}$. Following the idea of scattered factor $k$-universality, we investigate $m$-nearly $k$-universality, i.e., words where $m$ scattered factors of length $k$ are absent, w.r.t. Simon congruence. We present a full characterisation as well as the index of the congruence for $m=1$. For $m\neq 1$, we show some results if in addition $w$ is $(k-1)$-universal as well as some further insights for different $m$.