Combinatorial Properties of Periodic Patterns in Compressed Strings
-
- Englisch ausgewählt
14,90 €
inkl. gesetzl. MwSt.,
Beschreibung
Produktdetails
Einband
Taschenbuch
Erscheinungsdatum
10.10.2023
Abbildungen
Illustrationen
Verlag
Universitätsverlag ChemnitzSeitenzahl
154
Maße (B/H)
14,8/21 cm
Gewicht
248 g
Sprache
Englisch
ISBN
978-3-96100-191-0
Firstly, we consider maximal d-repetitions. These are substrings that are at least 2+d times as long as their minimum period.
Secondly, we consider 3-cadences. These are arithmetic subsequence of three equal characters.
Lastly, we consider maximal pairs. These are pairs of identical substrings.
Maximal d-repetitions and maximal pairs of uncompressed strings are already well-researched. However, no non-trivial upper bound for distinct occurrences of these patterns that take the compressed size of the underlying strings into account were known prior to this research.
We provide upper bounds for several variants of these two patterns that depend on the compressed size of the string, the logarithm of the string's length, the highest allowed power and d.
These results also lead to upper bounds and new insights for the compacted directed acyclic word graph and the run-length encoded Burrows-Wheeler transform.
We prove that cadences with three elements can be efficiently counted in uncompressed strings and can even be efficiently detected on grammar-compressed binary strings. We also show that even slightly more difficult variants of this problem are already NP-hard on compressed strings.
Along the way, we extend the underlying geometry of the convolution from rectangles to arbitrary polygons. We also prove that this non-rectangular convolution can still be efficiently computed.
Noch keine Bewertungen vorhanden
Verfassen Sie die erste Bewertung zu diesem Artikel
Helfen Sie anderen Kundinnen und Kunden durch Ihre Meinung.
Kurze Frage zu unserer Seite
Vielen Dank für dein Feedback
Wir nutzen dein Feedback, um unsere Produktseiten zu verbessern. Bitte habe Verständnis, dass wir dir keine Rückmeldung geben können. Falls du Kontakt mit uns aufnehmen möchtest, kannst du dich aber gerne an unseren Kund*innenservice wenden.
zum Kundenservice