Abstract We investigate the locality number, a recently introduced structural parameter for strings (with applications in pattern matching with variables), and its connection to two important graph-parameters, cutwidth and pathwidth. These connections allow us to show that computing the locality number is $$\textsf {NP}$$ NP -hard, but fixed-parameter tractable, if parameterised by the locality number or by the alphabet size, which has been formulated as open problems in the literature. Moreover, the locality number can be approximated with ratio $${{\,\textrm{O}\,}}(\sqrt{\log ({{\,\mathrm{\textsf {opt}}\,}})} \log (n))$$ O ( log ( opt ) log ( n ) ) . An important aspect of our work – that is relevant in its own right and of independent interest – is that we identify connections between the string parameter of the locality number on the one hand, and the famous graph parameters of cutwidth and pathwidth, on the other hand. These two parameters have been jointly investigated in the literature and are arguably among the most central graph parameters that are based on “linearisations” of graphs. In this way, we also identify a direct approximation preserving reduction from cutwidth to pathwidth, which shows that any polynomial $$f({{\,\mathrm{\textsf {opt}}\,}},|V|)$$ f ( opt , | V | ) -approximation algorithm for pathwidth yields a polynomial $$2f(2{{\,\mathrm{\textsf {opt}}\,}},h)$$ 2 f ( 2 opt , h ) -approximation algorithm for cutwidth on multigraphs (where h is the number of edges). In particular, this translates known approximation ratios for pathwidth into new approximation ratios for cutwidth, namely $${{\,\textrm{O}\,}}(\sqrt{\log ({{\,\mathrm{\textsf {opt}}\,}})} \log (h))$$ O ( log ( opt ) log ( h ) ) and $${{\,\textrm{O}\,}}(\sqrt{\log ({{\,\mathrm{\textsf {opt}}\,}})} {{\,\mathrm{\textsf {opt}}\,}})$$ O ( log ( opt ) opt ) for (multi) graphs with h edges.

A subsequence of a word w is a word u such that u = w [ i 1 ] w [ i 2 ] … w [ i k ] , for some set of indices 1 ≤ i 1 < i 2 < … < i k ≤ | w | . A word w is k -subsequence universal over an alphabet Σ if every word in Σ 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 Σ and regular languages over Σ. We call a regular language L k- ∃ -subsequence universal if there exists a k -subsequence universal word in L , and k- ∀ -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 k- ∃ -subsequence universal and, respectively, if it is k- ∀ -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 k- ∃ -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, non-deterministic) finite automaton, and ranking an input word (path) within the set of k -subsequence universal words accepted by a given finite automaton.

http://dx.doi.org/10.13039/501100001659 German Research Foundation

One of the most studied famous classes of words is the class of Lyndon words. Their studies are mainly motivated by the property that they factorise the free monoid as shown in the famous Chen-Fox-Lyndon Theorem. Several generalisations of Lyndon words as anti-Lyndon words, Nyldon words or inverse Lyndon words were made over time. In 2014, Grinberg introduced Nyldon words as a new perspective on the factorisation of the free monoid of words. In particular, for Nyldon words the famous Chen-Fox-Lyndon Theorem is considered w.r.t. a reversed lexicographical order, i.e., a lexicographically non-decreasing factorisation where each factor is smaller or equal than its successor. Further, a generalised lexicographical order is defined by equipping each position i in a word in Σ ⁎ with a total order ◃ i on Σ. For combining the concept of a generalised order as for generalised Lyndon words and the class of Nyldon words, we investigate a non-decreasing factorisation of the free monoid w.r.t. this generalised ordering and introduce generalised Nyldon words . We show that those words even force a unique non-decreasing factorisation, form a right Hall set, and coincide with the anti-Lyndon words.

Abstract Word-representable graphs were introduced in 2008 by Kitaev and Pyatkin in the context of semigroup theory. Graphs are called word-representable if there exists a word with the graph’s nodes as letters such that the letters in the word alternate iff there is an edge between them in the graph. Until today numerous works investigated the word-representability of graphs but mostly from the graph perspective. In this work, we change the perspective to the words, i.e., we take classes of words and investigate the represented graphs. Our first subject of interest are the conjugates of words: we determine exactly which graphs are represented if we rotate the word. Afterwards, we look at k-local words introduced by Day et al. (FSTTCS LIPIcs, 2017) in order to gain more insights into this class of words. Here, we investigate especially which graphs are represented by 1-local words. Lastly, we prove that the language of all words representing a graph is regular. We were also able to characterise k-representable graphs, solving an open problem.

A subsequence of a word w is a word u such that u = w[i₁] w[i₂] … w[i_k], for some set of indices 1 ≤ i₁ < i₂ < … < i_k ≤ |w|. A word w is k-subsequence universal over an alphabet Σ if every word in Σ^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 Σ and regular languages over Σ. We call a regular language L k-∃-subsequence universal if there exists a k-subsequence universal word in L, and k-∀-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 k-∃-subsequence universal and, respectively, if it is k-∀-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 k-∃-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.

A word u is a subsequence of another word w if u can be obtained from w by deleting some of its letters. In the early 1970s, Imre Simon defined the relation ∼_k (called now Simon-Congruence) as follows: two words having exactly the same set of subsequences of length at most k are ∼_k-congruent. This relation was central in defining and analysing piecewise testable languages, but has found many applications in areas such as algorithmic learning theory, databases theory, or computational linguistics. Recently, it was shown that testing whether two words are ∼_k-congruent can be done in optimal linear time. Thus, it is a natural next step to ask, for two words w and u which are not ∼_k-equivalent, what is the minimal number of edit operations that we need to perform on w in order to obtain a word which is ∼_k-equivalent to u. In this paper, we consider this problem in a setting which seems interesting: when u is a k-subsequence universal word. A word u with alph(u) = Σ is called k-subsequence universal if the set of subsequences of length k of u contains all possible words of length k over Σ. As such, our results are a series of efficient algorithms computing the edit distance from w to the language of k-subsequence universal words.

We investigate the locality number, a recently introduced structural parameter for strings (with applications in pattern matching with variables), and its connection to two important graph-parameters, cutwidth and pathwidth. These connections allow us to show that computing the locality number is NP-hard but fixed-parameter tractable (when the locality number or the alphabet size is treated as a parameter), and can be approximated with ratio O(sqrt{log{opt}} log n). As a by-product, we also relate cutwidth via the locality number to pathwidth, which is of independent interest, since it improves the best currently known approximation algorithm for cutwidth. In addition to these main results, we also consider the possibility of greedy-based approximation algorithms for the locality number.