String Periods in the Order-Preserving Model

DOI10.4230/LIPICS.STACS.2018.38MaRDI QIDQ3304137zbMATH OpenOpenAlexFDO

Authors Garance Gourdel, Tomasz Kociumaka, Arseny M. Shur, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń

Publication date 5 August 2020

Full work available at URL https://arxiv.org/abs/1801.01404

zbMATH Keywords

efficient algorithmorder-preserving pattern matchingperiod

Mathematics Subject Classification ID

Algorithms on strings (68W32) Analysis of algorithms (68W40)

Abstract: The order-preserving model (op-model, in short) was introduced quite recently but has already attracted significant attention because of its applications in data analysis. We introduce several types of periods in this setting (op-periods). Then we give algorithms to compute these periods in time $O(n)$, $O(nloglogn)$, $O(nlo{g}^{2}logn/logloglogn)$, $O(nlogn)$ depending on the type of periodicity. In the most general variant the number of different periods can be as big as $Omega(n^2)$, and a compact representation is needed. Our algorithms require novel combinatorial insight into the properties of such periods.

Recommendations

• String periods in the order-preserving model
• scientific article; zbMATH DE number 3907795
• scientific article; zbMATH DE number 1092948
• scientific article; zbMATH DE number 2185637
• Approximate periods of strings
• scientific article; zbMATH DE number 1615296
• scientific article; zbMATH DE number 1754624
• Order preserving vibrating strings and applications to electrodynamics and magnetohydrodynamics
• Inferring strings from full abelian periods
• Periodicity and roots of transfinite strings

Cites work

• A fast algorithm for order-preserving pattern matching
• A filtration method for order-preserving matching
• A linear time algorithm for consecutive permutation pattern matching
• A note on easy and efficient computation of full abelian periods of a word
• A note on efficient computation of all abelian periods in a string
• Abelian periods, partial words, and an extension of a theorem of Fine and Wilf
• Algorithms for computing abelian periods of words
• An encoding for order-preserving matching
• Consecutive patterns in permutations
• Efficient algorithms for the order preserving pattern matching problem
• Fast algorithms for abelian periods in words and greatest common divisor queries
• Fast algorithms for abelian periods in words and greatest common divisor queries
• Fine and Wilf words for any periods
• Fine and Wilf's theorem for three periods and a generalization of Sturmian words
• Generalized pattern matching and periodicity under substring consistent equivalence relations
• Graph connectivity, partial words, and a theorem of Fine and Wilf
• scientific article; zbMATH DE number 5605094 (Why is no real title available?)
• scientific article; zbMATH DE number 3523640 (Why is no real title available?)
• scientific article; zbMATH DE number 1834684 (Why is no real title available?)
• Introduction to algorithms.
• Jewels of Stringology
• On a paper by Castelli, Mignosi, Restivo
• Order-preserving indexing
• Order-preserving matching
• Order-preserving pattern matching with \(k\) mismatches
• Partial words and a theorem of Fine and Wilf
• Partial words and a theorem of Fine and Wilf revisited
• Partial words and the interaction property of periods
• Periodic partial words and random bipartite graphs
• Periodicity and repetitions in parameterized strings
• Single and multiple consecutive permutation motif search
• Subquadratic-time algorithms for abelian stringology problems
• Uniqueness Theorems for Periodic Functions

Cited in

(4)

• Finding patterns and periods in Cartesian tree matching
• String periods in the order-preserving model
• Cartesian Tree Matching and Indexing
• Observed Periodicity Related to the Four-Strand Burau Representation

This page was built for publication: String Periods in the Order-Preserving Model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3304137)