Efficiently Finding All Minimal and Shortest Absent Subsequences in a String

Florin Manea, Tina Ringleb, Stefan Siemer, Maximilian Winkler · 2025

Read Efficiently Finding All Minimal and Shortest Absent Subsequences in a String by Florin Manea, Tina Ringleb, Stefan Siemer, Maximilian Winkler (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-21471.txt.

Introduction

Some letter strings hide inside a longer string, and some never appear at all. Florin Manea, Tina Ringleb, Stefan Siemer, and Maximilian Winkler study the missing ones in a 2025 paper. A subsequence keeps the order of letters while dropping others. An absent subsequence is one that cannot be formed that way. Past work focused on the shortest absent ones and the minimal ones.

The authors give the fastest possible methods to list all shortest and all minimal absent subsequences. A second set of methods lists them step by step, showing only the small edit from one to the next. They also give a fast way to find the longest minimal absent one. All three results improve the best methods known before.

Catalog record

CREATORFlorin Manea, Tina Ringleb, Stefan Siemer, Maximilian Winkler
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE118 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-21471

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Efficiently Finding All Minimal and Shortest Absent Subsequences in a String Florin Manea, Tina Ringleb, Stefan Siemer, Maximilian Winkler Abstract Given a string w w , another string v v is said to be a subsequence of w w if v v can be obtained from w w by removing some of its letters; on the other hand, v v is called an absent subsequence of w w if v v is not a subsequence of w w . The existing literature on absent subsequences focused on understanding, for a string w w , the set of its shortest absent subsequences (i.e., the shortest strings which are absent subsequences of w w ) and that of its minimal absent subsequences (i.e., those strings which are absent subsequences of w w but whose every proper subsequence occurs in w w ). Our contributions to this area of research are the following. Firstly, we present optimal algorithms (with linear time preprocessing and output-linear delay) for the enumeration of the shortest and, respectively, minimal absent subsequences. Secondly, we present optimal algorithms for the incremental enumeration of these strings with linear time preprocessing and constant delay; in this setting, we only output short edit-scripts showing how the currently enumerated string differs from the previous one. Finally, we provide an efficient algorithm for identifying a longest minimal absent subsequence of a string. All our algorithms improve the state-of-the-art results for the aforementioned problems. Department of Computer Science, University of Göttingen, [email protected]://orcid.org/0000-0001-6094-3324This work was supported by the German Research Foundation (DFG), project number 466789228 (Heisenberg grant). Department of Computer Science, University of Göttingen, [email protected] Department of Computer Science, University of Göttingen, [email protected]://orcid.org/0000-0001-7509-8135 Department of Computer Science, University of Göttingen, [email protected] keywords Subsequences, Absent Subsequences, Shortest Absent Subsequences, Minimal Absent Subsequences, Enumeration Algorithms ccs Theory of computation Data structures design and analysis † † runningauthor: Manea et al. † † runningtitle: Efficiently Finding All Minimal and Shortest Absent Subsequences † † copyright: CC-BY † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction A string v of length \ell is a subsequence of a string w if there exist (possibly empty) strings x_{1},\ldots,x_{\ell+1} and letters v_{1},\ldots,v_{\ell} such that v=v_{1}\cdots v_{\ell} and w=x_{1}v_{1}\cdots x_{\ell}v_{\ell}x_{\ell+1} . In other words, v can be obtained from w by removing some of its letters. The concept of subsequence (also called scattered factor, or subword) appears and plays important roles in many different areas of computer science: in combinatorics on strings [ 52 , 32 , 48 , 54 ] , formal languages [ 56 , 57 , 38 , 2 , 27 ] and automata theory [ 36 , 61 , 62 ] . Aside from that, subsequences are important objects of study also in the area of algorithm-design. On the one hand, they appear in string-algorithmic problems, such as computing the longest common subsequences or the shortest common supersequences (see the survey [ 14 ] and the references therein) or the testing of the Simon’s congruence of strings (see [ 58 , 34 ] and the references therein). On the other hand, the combinatorial and algorithmic study of subsequences (or patterns) occurring in permutations (such as, e.g., longest increasing subsequences [ 29 ] ) is an important and classical topic of research (see, e.g., [ 39 , 45 , 53 ] ). For a more detailed discussion regarding combinatorial pattern matching problems related to subsequences see the survey [ 42 ] . Moreover, algorithmic problems on subsequences were revisited in the context of fine-grained complexity [ 17 , 1 ] , and lower bounds for their complexity were shown. Nevertheless, subsequences also appear in more applied settings: for modeling concurrency [ 51 , 55 ] , in database theory, in settings related to event stream processing [ 8 , 35 , 63 ] , in data mining [ 43 , 44 ] , or in problems related to bioinformatics [ 16 ] . These applications led to new theoretical results (algorithms and fine-grained complexity lower bounds) as well. For instance, in connection to the database connection, mentioned above, we recall the study of constrained subsequences of strings, where the substrings occurring between the positions of the subsequence are constrained by regular or length constraints [ 26 , 5 , 47 ] . This paper is centered around the notion of absent subsequence , introduced in [ 40 ] . A string v is an absent subsequence of a string w if v is not a subsequence of w . The main motivation of [ 40 ] for the study of absent subsequences was related to the congruence \sim_{k} (called Simon’s Congruence, see, e.g., [ 56 , 50 ] ) between strings having exactly the same set of subsequences of length at most k . The problems of deciding whether two given strings are \sim_{k} -equivalent, for a given k , and to find the largest k such that two given strings are \sim_{k} -equivalent (and their applications) were heavily investigated in the literature, with optimal solutions for both these problems being obtained recently (see [ 34 ] and the references therein). One of the central ingredients in many of these works was the notion of a distinguishing string, i.e., the shortest subsequence present in one string and absent from the other. Along the same lines, and very close to the study of Simon’s congruence, is the study of m -nearly k -universal strings, where one is considering strings which contain as subsequences all strings of length k , except exactly m such strings, which are, therefore, absent [ 28 ] . The other main motivation for investigating absent subsequences was the study of missing factors (or missing substrings) in strings, where the focus is on the set of strings which are not substrings (or factors) of w . The study of missing factors ranges from practical applications [ 18 , 20 , 24 ] to theoretical results of combinatorial [ 15 , 23 , 49 ] or algorithmic nature [ 9 , 11 , 22 , 33 ] . Last but not least, while subsequences are used to model sequences of events occurring in a string or a stream, formalising the trace of a computation, absent subsequences correspond, similarly, to sequences of events avoided by the respective computation-trace. On a related note, absent subsequences also naturally occur in the study of patterns avoided by permutations [ 39 ] , with the important difference that a permutation is essentially a string whose letters are pairwise distinct. Two classes of absent subsequences were investigated in the seminal paper [ 40 ] and subsequent works [ 41 , 59 , 3 ] . On the one hand, we have the class of shortest absent subsequences of a string, namely the absent subsequences of minimal length of that string. On the other hand, we have the class of minimal absent subsequences of a string w : the absent

Read the complete text