Maria Kosche ; Tore Koß ; Florin Manea ; Stefan Siemer - Absent Subsequences in Words

fi:9221 - Fundamenta Informaticae, October 14, 2023, Volume 189, Issues 3-4: Reachability Problems 2020 and 2021
Absent Subsequences in WordsArticle

Authors: Maria Kosche ; Tore Koß ; Florin Manea ; Stefan Siemer

    An absent factor of a string $w$ is a string $u$ which does not occur as a contiguous substring (a.k.a. factor) inside $w$. We extend this well-studied notion and define absent subsequences: a string $u$ is an absent subsequence of a string $w$ if $u$ does not occur as subsequence (a.k.a. scattered factor) inside $w$. Of particular interest to us are minimal absent subsequences, i.e., absent subsequences whose every subsequence is not absent, and shortest absent subsequences, i.e., absent subsequences of minimal length. We show a series of combinatorial and algorithmic results regarding these two notions. For instance: we give combinatorial characterisations of the sets of minimal and, respectively, shortest absent subsequences in a word, as well as compact representations of these sets; we show how we can test efficiently if a string is a shortest or minimal absent subsequence in a word, and we give efficient algorithms computing the lexicographically smallest absent subsequence of each kind; also, we show how a data structure for answering shortest absent subsequence-queries for the factors of a given string can be efficiently computed.


    Volume: Volume 189, Issues 3-4: Reachability Problems 2020 and 2021
    Published on: October 14, 2023
    Accepted on: October 6, 2023
    Submitted on: March 16, 2022
    Keywords: Computer Science - Formal Languages and Automata Theory,Computer Science - Data Structures and Algorithms

    Consultation statistics

    This page has been seen 146 times.
    This article's PDF has been downloaded 120 times.