Identifying periodic patterns in time series data is crucial for uncovering hidden structures and predicting future events. Recognizing meaningful periodic patterns in real data requires handling approximation criteria since periodic phenomena are usually inexact. This paper introduces a suitable criterion and focuses on detecting Consecutive Periodic Patterns (CPPs) with$k \Delta$-errors, where$k$bounds the number of errors and$\Delta$limits the size of the error. We develop efficient algorithms to detect the Longest Pure Consecutive Maximal Periodic Pattern with bounded errors in both raw and compressed data, the latter by means of the Arithmetic Progressions Tree (APT) data structure.

This paper introduces a novel explainable artificial intelligence (XAI) approach based on near-misses analysis (NMA). This approach uses the network close related predictions to reveal a hierarchy of logical concepts inferred from the latent decision-making process of a neural network (NN) without delving into its explicit structure. Several NMA usage possibilities are reported in this paper. First, it serves to create an explanation in the form of a gradually expanding explicit linked concepts which coupled with a proper dictionary can provide a scoring method to differentiate which of any given models is better at providing human-like conceptual explanations. In addition, NMA can be used to pinpoint how to improve models according to their explanatory outcome. Finally, it enables to detect adversarial attacks. The proposed XAI approach is examined on different network architectures that vary in size and shape (ResNet, VGG, EfficientNet, MobileNet) and on several datasets which were already organized in a hierarchical concept structure (ImageNet, CIFAR100). Results demonstrate that NMA can reflect NNs latent concepts generation process. Moreover, using the devised scoring method, it is reported that efficient architectures, which achieve a similar accuracy level with less neurons, may still pay the price of explainability and robustness. • Introduce a new XAI method based on neural networks concepts generation. • Demonstrate the explanatory capabilities of this method on various models and datasets. • Propose a new explanatory scoring method. • Demonstrate how to use the new method for model debugging. • Demonstrate how to use the new method for detecting adversarial attacks.

The Arithmetic Progressions Tree (APT) is a data structure storing an encoding of a monotonic sequence$\mathcal{L}$in$[1..n]$. While previous work on$\mathsf{APT}$focused on its theoretical and experimental compression guarantees, recently, it was shown that searches of sub-sequences, runs and periodic patterns over the$\mathsf{APT}$compressed data can be applied. This paper extends the set of supported operations and focuses on the computation of consecutively maximal periodic patterns directly over the APT. In particular, given the$\mathsf{APT}$compressed representation of$\mathcal{L}$, we show how: (1)One can find if a consecutive periodic pattern with difference$d_{P}$is represented by an$\mathsf{APT}$node in time$O(\log n)$and if positive, report its occurrences in$\mathcal{L}$in time proportional to the output size multiplied by$\log d_{P}$and the size of the$\mathsf{APT}$compressed representation of$\mathcal{L}$, while assuring that every reported consecutive occurrence is consecutively maximal. (2)Given a query periodic pattern difference,$d_{P}$, we can give a one-sided$O(\log d_{P})$-additive approximation for the length of the consecutively maximal periodic pattern with difference$d_{P}$that occurs in$\mathcal{L}$in time$O(\log n)$. (3)We give a one-sided$O(\log n)$-additive approximation for the maximum length of a consecutively maximal periodic pattern that occurs in$\mathcal{L}$in time$O(\sqrt{n}\log n)$.

This paper studies partial permutations and their use in algorithmic tasks. A partial permutation over Σ is a bijection π p a r : Σ 1 ↦ Σ 2 mapping a subset Σ 1 ⊂ Σ to a subset Σ 2 ⊂ Σ , where | Σ 1 | = | Σ 2 | ( | Σ | denotes the size of a set Σ). Intuitively, two partial permutations agree if their mapping pairs do not form conflicts . We formally define this notion enabling a consistent as well as informatively rich comparison between partial permutations. We define the Partial Permutations Agreement problem (PPA), as follows. Given two sets A 1 , A 2 of partial permutations over alphabet Σ, each of size n , output a pair ( π i , π j ) , where π i ∈ A 1 , π j ∈ A 2 and π i agrees with π j , if exists. We study the existence of a data structure for efficiently maintaining a dynamic set of partial permutations enabling to retrieve agreement of partial permutations giving both negative and positive results. As applications we point out: (1) fruitful/futile methods for efficient genes sequences comparison in database, (2) an automatic color transformation data augmentation technique for image processing through neural networks, (3) negatively answer a recently posed open question on the strict parameterized dictionary matching with one gap (PDMOG) problem over general dictionary alphabets.

The Arithmetic Progressions Tree (APT) is an encoding of a monotonic sequence ℒ in [1..n]. Previous work on APT coding focused on its theoretical and experimental compression guarantees. This paper is the first to consider computations over APT compressed data. In particular: (1) We show how to perform a search for any sub-sequence of the monotone sequence ℒ in time proportional to the query sub-sequence length multiplied by the size of the APT compressed representation of ℒ. (2) We show how, given the APT compressed representation of the monotone sequence ℒ, we can find a minimum run-length of ℒ in constant time, a maximum run-length of ℒ in O(log n) time, and all runs of ℒ in constant time plus the output size. (3) Most importantly, we show how, given the APT compressed representation of the monotone sequence ℒ, we can answer whether a periodic pattern P appears in ℒ in O(log n) time and report its locations in the output size time. (4) In addition, we improve the APT construction algorithm time and space complexity.

This paper focuses on the concept of partial permutations and their use in algorithmic tasks. A partial permutation over Σ is a bijection π_{par}: Σ₁↦Σ₂ mapping a subset Σ₁ ⊂ Σ to a subset Σ₂ ⊂ Σ, where |Σ₁| = |Σ₂| (|Σ| denotes the size of a set Σ). Intuitively, two partial permutations agree if their mapping pairs do not form conflicts. This notion, which is formally defined in this paper, enables a consistent as well as informatively rich comparison between partial permutations. We formalize the Partial Permutations Agreement problem (PPA), as follows. Given two sets A₁, A₂ of partial permutations over alphabet Σ, each of size n, output all pairs (π_i, π_j), where π_i ∈ A₁, π_j ∈ A₂ and π_i agrees with π_j. The possibility of having a data structure for efficiently maintaining a dynamic set of partial permutations enabling to retrieve agreement of partial permutations is then studied, giving both negative and positive results. Applying our study enables to point out fruitful versus futile methods for efficient genes sequences comparison in database or automatic color transformation data augmentation technique for image processing through neural networks. It also shows that an efficient solution of strict Parameterized Dictionary Matching with One Gap (PDMOG) over general dictionary alphabets is not likely, unless the Strong Exponential Time Hypothesis (SETH) fails, thus negatively answering an open question posed lately.

Regularities in strings arise in various areas of science, including coding and automata theory, formal language theory, combinatorics, molecular biology and many others. A common notion to describe regularity in a string T is a cover, which is a string C for which every letter of T lies within some occurrence of C. The alignment of the cover repetitions in the given text is called a tiling. In many applications finding exact repetitions is not sufficient, due to the presence of errors. In this paper, we use a new approach for handling errors in coverable phenomena and define the approximate cover problem (ACP), in which we are given a text that is a sequence of some cover repetitions with possible mismatch errors, and we seek a string that covers the text with the minimum number of errors. We first show that the ACP is NP-hard, by studying the cover-length relaxation of the ACP, in which the requested length of the approximate cover is also given with the input string. We show that this relaxation is already NP-hard. We also study another two relaxations of the ACP, which we call the partial-tiling relaxation of the ACP and the full-tiling relaxation of the ACP, in which a tiling of the requested cover is also given with the input string. A given full tiling retains all the occurrences of the cover before the errors, while in a partial tiling there can be additional occurrences of the cover that are not marked by the tiling. We show that the partial-tiling relaxation has a polynomial time complexity and give experimental evidence that the full-tiling also has polynomial time complexity. The study of these relaxations, besides shedding another light on the complexity of the ACP, also involves a deep understanding of the properties of covers, yielding some key lemmas and observations that may be helpful for a future study of regularities in the presence of errors.

Tracing regularities plays a key role in data analysis for various areas of science, including coding and automata theory, formal language theory, combinatorics, molecular biology and many others. Part of the scientific process is understanding and explaining these regularities. A common notion to describe regularity in a string T is a cover or quasi-period, which is a string C for which every letter of T lies within some occurrence of C. In many applications finding exact repetitions is not sufficient, due to the presence of errors. In this paper we initiate the study of quasi-periodicity persistence under mismatch errors, and our goal is to characterize situations where a given quasi-periodic string remains quasi-periodic even after substitution errors have been introduced to the string. Our study results in proving necessary conditions as well as a theorem stating sufficient conditions for quasi-periodicity persistence. As an application, we are able to close the gap in understanding the complexity of Approximate Cover Problem (ACP) relaxations studied by [Amir 2017a, Amir 2017b] and solve an open question.

Data analysis typically involves error recovery and detection of regularities as two different key tasks. In this paper we show that there are data types for which these two tasks can be powerfully combined. A common notion of regularity in strings is that of a cover. Data describing measures of a natural coverable phenomenon may be corrupted by errors caused by the measurement process, or by the inexact features of the phenomenon itself. Due to this reason, different variants of approximate covers have been introduced, some of which are NP-hard to compute. In this paper we assume that the Hamming distance metric measures the amount of corruption experienced, and study the problem of recovering the correct cover from data corrupted by mismatch errors, formally defined as the cover recovery problem (CRP). We show that for the Hamming distance metric, coverability is a powerful property allowing detecting the original cover and correcting the data, under suitable conditions. We also study a relaxation of another problem, which is called the approximate cover problem (ACP). Since the ACP is proved to be NP-hard [Amir,Levy,Lubin,Porat, CPM 2017], we study a relaxation, which we call the candidate-relaxation of the ACP, and show it has a polynomial time complexity. As a result, we get that the ACP also has a polynomial time complexity in many practical situations. An important application of our ACP relaxation study is also a polynomial time algorithm for the cover recovery problem (CRP).

We examine the complexity of the online Dictionary Matching with One Gap Problem (DMOG) which is the following. Preprocess a dictionary D of d patterns, where each pattern contains a special gap symbol that can match any string, so that given a text that arrives online, a character at a time, we can report all of the patterns from D that are suffixes of the text that has arrived so far, before the next character arrives. In more general versions the gap symbols are associated with bounds determining the possible lengths of matching strings. Online DMOG captures the difficulty in a bottleneck procedure for cyber-security, as many digital signatures of viruses manifest themselves as patterns with a single gap. In this paper, we demonstrate that the difficulty in obtaining efficient solutions for the DMOG problem, even in the offline setting, can be traced back to the infamous 3SUM conjecture. We show a conditional lower bound of Omega(delta(G_D)+op) time per text character, where G_D is a bipartite graph that captures the structure of D, delta(G_D) is the degeneracy of this graph, and op is the output size. Moreover, we show a conditional lower bound in terms of the magnitude of gaps for the bounded case, thereby showing that some known offline upper bounds are essentially optimal. We also provide matching upper-bounds (up to sub-polynomial factors), in terms of the degeneracy, for the online DMOG problem. In particular, we introduce algorithms whose time cost depends linearly on delta(G_D). Our algorithms make use of graph orientations, together with some additional techniques. These algorithms are of practical interest since although delta(G_D) can be as large as sqrt(d), and even larger if G_D is a multi-graph, it is typically a very small constant in practice. Finally, when delta(G_D) is large we are able to obtain even more efficient solutions.

Assume that a natural cyclic phenomenon has been measured, but the data is corrupted by errors. The type of corruption is application-dependent and may be caused by measurements errors, or natural features of the phenomenon. We assume that an appropriate metric exists, which measures the amount of corruption experienced. This article studies the problem of recovering the correct cycle from data corrupted by various error models, formally defined as the period recovery problem . Specifically, we define a metric property which we call pseudolocality and study the period recovery problem under pseudolocal metrics. Examples of pseudolocal metrics are the Hamming distance, the swap distance, and the interchange (or Cayley) distance. We show that for pseudolocal metrics, periodicity is a powerful property allowing detecting the original cycle and correcting the data, under suitable conditions. Some surprising features of our algorithm are that we can efficiently identify the period in the corrupted data, up to a number of possibilities logarithmic in the length of the data string, even for metrics whose calculation is NP-hard . For the Hamming metric, we can reconstruct the corrupted data in near-linear time even for unbounded alphabets. This result is achieved using the property of separation in the self-convolution vector and Reed-Solomon codes. Finally, we employ our techniques beyond the scope of pseudo-local metrics and give a recovery algorithm for the non-pseudolocal Levenshtein edit metric.

Consider the following optimization problem: given two strings over the same alphabet, transform one into another by a succession of interchanges of two elements. In each interchange the two participating elements exchange positions. An interchange is given a weight that depends on the distance in the string between the two exchanged elements. The object is to minimize the total weight of the interchanges. This problem is a generalization of a classical problem on permutations (where every element appears once). The generalization considers general strings with possibly repeating elements, and a function assigning weights to the interchanges. The generalization to general strings (with unit weights) was mentioned by Cayley in the 19th century, and its complexity has been an open question since. We solve this open problem and consider various weight functions as well.