Eintrag in der Universitätsbibliographie der TU Chemnitz
Volltext zugänglich unter
URN: urn:nbn:de:bsz:ch1-qucosa2-864421
Pape-Lange, Julian
Goerdt, Andreas (Dr. rer. nat.); Bartholdi, Laurent (Prof.); Meer, Klaus (Prof. Dr. rer. nat. habil.)
Combinatorial Properties of Periodic Patterns in Compressed Strings
Kurzfassung in deutsch
Die hier zu verteidigende Dissertation beschäftigt sich mit kombinatorischen und algorithmischen Problemen zu einigen periodischen Textmustern. In dieser Disputation wird ein Textmuster vorgestellt, dessen Zählalgorithmus wegen seiner Vielseitigkeit von allgemeinem Interesse ist und erstmals von uns auf dem 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) in internationaler Zusammenarbeit mit Mitsuru Funakoshi von der Kyushu-Universität veröffentlicht wurde.Die diskrete azyklische Faltung ist eine Operation, die zwei Vektoren a und b der Länge n bekommt und die 2n+1 Summen mit Summanden der Form a_i * b_{k-i} berechnet. Es ist bekannt, dass die Faltung mit Hilfe der schnellen Fourier-Transformation oder der schnellen zahlentheoretischen Transformation in O(n log n) Operationen berechnet werden kann. Diese Dissertation erweitert die Faltung, indem wir für ein Polygon P die Summen auf die Summanden einschränken, deren Indexpaar in P liegt. Für ein Polygon mit k Eckpunkten und Umfang p braucht diese Faltung immer noch nur O(k+p(log p)^2 log k) Operationen.
Die Faltung und ihre nicht-rechteckige Erweiterung können verwendet werden, um kurze arithmetische Progressionen {i, i+d, i+2d} zu finden, deren zugehörige Zeichen im Text übereinstimmen. Obwohl diese Strukturen bereits von van der Waerden in den 1920er Jahren studiert wurden, war noch kein Algorithmus zum Zählen dieser "3-Subkadenzen" mit subquadratischer Laufzeit bekannt. In dieser Dissertation zeigen wir, dass sich 3-Subkadenzen und einige ihrer Varianten in quasilinearer Zeit zählen lassen.
Kurzfassung in englisch
The dissertation which is defended here deals with combinatoric and algorithmic problems of periodic string patterns. In this disputation, we present a string pattern which has a counting algorithm that is of general interest because of its versatility. We previously published this algorithm at the 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) in international collaboration with Mitsuru Funakoshi from Kyushu university.The discrete acyclic convolution is an operation that takes two vectors a and b of length n and calculates the 2n+1 sums with addends of the form a_i * b_{k-i}. It is well-known that the convolution can be calculated by fast Fourier transform or fast number theoretic transform in O(n log n) operations. This dissertation extends the convolution by restricting the sums to addends whose index pair lie in a polygon P. For polygons with k vertices and perimeter p, this non-rectangular convolution only needs O(k+p(log p)^2 log k) operations.
The convolution and its non-rectangular extension can be used to find short arithmetic progressions {i, i+d, i+2d} whose corresponding characters in the string are equal. Although these structures were already studied by van der Waerden in the 1920s, there was no known algorithm for counting these "3-subcadences" in subquadratic time. In this dissertation, we prove that 3-subcadence and several of their variants can be counted in quasilinear time.
| Universität: | Technische Universität Chemnitz | |
| Institut: | Professur Theoretische Informatik | |
| Fakultät: | Fakultät für Informatik | |
| Dokumentart: | Dissertation | |
| Betreuer: | Goerdt, Andreas (Dr. rer. nat.) | |
| ISBN/ISSN: | 9783961001910 | |
| DOI: | doi:10.51382/978-3-96100-191-0 | |
| URL/URN: | urn:nbn:de:bsz:ch1-qucosa2-864421 | |
| Quelle: | Chemnitz : Universitätsverlag Chemnitz, 2023. - viii, 154 S. | |
| SWD-Schlagwörter: | Kombinatorik , Algorithmus , Textkompression , Mustererkennung | |
| Freie Schlagwörter (Englisch): | Combinatorics , Combinatorial Algorithms , Highly Compressible Strings , Discrete Acyclic Convolution , Maximal delta-Repetitions , Maximal Repetitions , Maximal Subrepetitions , Cadences , Subcadences , Maximal Pairs , Maximal Repeats | |
| DDC-Sachgruppe: | Datenverarbeitung; Informatik | |
| Sprache: | englisch | |
| Tag der mündlichen Prüfung | 03.07.2023 | |
| OA-Lizenz | CC BY 4.0 |
