Absent Subsequences in Words

• Autorzy: Kosche Maria , Koß Tore , Manea Florin , Siemer Stefan

Identyfikatory

DOI

10.3233/FI-222159

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Absent subsequence; Arch-factorization; Stringology Subsequence; Subsequence- Universality.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2022
• Tom: Vol. 189, nr 3-4
• Strony: 199--240
• Opis fizyczny: Bibliogr.

Twórcy

autor

Kosche Maria

• Institute for Computer Science Georg-August University G¨ottingen, Germany

autor

Koß Tore

• Institute for Computer Science Georg-August University G¨ottingen, Germany

autor

Manea Florin

• Institute for Computer Science Georg-August University G¨ottingen, Germany

autor

Siemer Stefan

• Institute for Computer Science Georg-August University G¨ottingen, Germany