Arrow Research search

Author name cluster

Amihood Amir

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

52 papers
2 author rows

Possible papers

52

TCS Journal 2024 Journal Article

On suffix tree detection

  • Amihood Amir
  • Eitan Kondratovsky
  • Avivit Levy

A suffix tree is a fundamental data structure for string processing and information retrieval, however, its structure is still not well understood. The suffix trees reverse engineering problem, which its research aims at reducing this gap, is the following. Given an ordered rooted tree T with unlabeled edges, determine whether there exists a string w such that the unlabeled-edges suffix tree of w is isomorphic to T. Previous studies on this problem consider the relaxation of having the suffix links as well as assume a binary alphabet. This paper is the first to consider the suffix tree detection problem, in which the relaxation of having suffix links as input is removed. We study suffix tree detection on two scenarios that are interesting per se. We provide a suffix tree detection algorithm for general alphabet periodic strings. Given an ordered tree T with n leaves, our detection algorithm takes O ( n + | Σ | p ) -time, where p is the unknown in advance length of a period that repeats at least 3 times in a string S having a suffix tree structure identical to T, if such S exists. Therefore, it is a polynomial time algorithm if p is a constant and a linear time algorithm if, in addition, the alphabet has a sub-linear size. We also show some necessary (but insufficient) conditions for binary alphabet general strings suffix tree detection. By this we take another step towards understanding suffix trees structure.

Details DOI

TCS Journal 2024 Journal Article

Reconstructing parameterized strings from parameterized suffix and LCP arrays

  • Amihood Amir
  • Eitan Kondratovsky
  • Gad M. Landau
  • Shoshana Marcus
  • Dina Sokol

Reconstructing input from a data structure entails determining whether an instance of the data structure is in fact valid or not, and if valid, discovering the underlying data that it represents. In this paper we consider the parameterized suffix array (pSA) along with its corresponding parameterized longest-common-prefix (pLCP) array and solve the following problem. Given two arrays of numbers as input, A and P, does there exist a parameterized string S such that A is its pSA and P is its pLCP array? If the answer is positive, our algorithm produces a string S whose pSA is A and whose pLCP array is P. Although the naive approach would have to consider an exponential number of possibilities for such a string S, our algorithm's time complexity is only O ( n 2 ) for input arrays of size n.

Details DOI

TCS Journal 2021 Journal Article

Towards a real time algorithm for parameterized longest common prefix computation

  • Amihood Amir
  • Eitan Kondratovsky

Parameterized matching has proven to be an efficient and useful tool for detecting code duplications. This paper presents a technique for calculating parameterized Longest Common Prefix ( p l c p ) in constant time based on the knowledge about the p l c p of the following suffixes. Using this technique, online p-suffix tree construction can be done in worst case time O ( log ⁡ n ) per input symbol. Searching for a pattern of length m in the resulting suffix tree takes O ( min ⁡ { m log ⁡ ( | Σ | + | Π | ), m + log ⁡ n } + m τ Π + t o c c ) time, where t o c c is the number of occurrences of the pattern, and τ Π depends on Π. For constant-sized Π, τ Π = 1, for polynomial-sized Π, τ Π = log ⁡ log ⁡ | Π |, and for unbounded Π, τ Π = log ⁡ | Π |.

Details DOI

TCS Journal 2020 Journal Article

Finding patterns and periods in Cartesian tree matching

  • Sung Gwan Park
  • Magsarjav Bataa
  • Amihood Amir
  • Gad M. Landau
  • Kunsoo Park

We introduce a new metric of match, called Cartesian tree matching, which means that two strings match if they have the same Cartesian trees. Based on Cartesian tree matching, we define single pattern matching, multiple pattern matching, and indexing problems. We propose a linear time algorithm for single pattern matching, and randomized linear time algorithms for multiple pattern matching and indexing. We also define three types of periods, called full period, initial period, and general period. We propose O ( n ) time, O ( n log ⁡ log ⁡ n ) time, and O ( n log ⁡ n ) time algorithms for finding all the full periods, initial periods, and general periods of a string of length n, respectively. Our efficient algorithms use a representation of the Cartesian tree, called parent-distance representation.

Details DOI

I&C Journal 2020 Journal Article

Online recognition of dictionary with one gap

  • Amihood Amir
  • Avivit Levy
  • Ely Porat
  • B. Riva Shalom

We formalize and examine the online Dictionary Recognition with One Gap problem (DROG) which is the following. Preprocess a dictionary D of d patterns each containing a special gap symbol that matches any string, so that given a text arriving online a character at a time, all patterns from D which are suffixes of the text that has arrived so far and have not been reported yet, are reported before the next character arrives. The gap symbols are associated with bounds determining possible lengths of matching strings. Online DROG captures the difficulty in a bottleneck procedure for cyber-security, as many digital signatures of viruses manifest themselves as patterns with a single gap. Following the work on the closely related online Dictionary Matching with One Gap problem (DMOG), we provide algorithms whose time cost depends linearly on δ ( G D ), where G D is a bipartite graph that captures the structure of D and δ ( G D ) is the degeneracy of this graph. These algorithms are of practical interest since although δ ( G D ) can be as large as d, and even larger if G D is a multi-graph, it is typically a small constant in practice.

Details DOI

TCS Journal 2020 Journal Article

Two-dimensional maximal repetitions

  • Amihood Amir
  • Gad M. Landau
  • Shoshana Marcus
  • Dina Sokol

Maximal repetitions or runs in strings have a wide array of applications and thus have been extensively studied. In this paper, we extend this notion to 2-dimensions, precisely defining a maximal 2D repetition. We provide initial bounds on the number of maximal 2D repetitions that can occur in an n × n array. The main contribution of this paper is the presentation of the first algorithm for locating all maximal 2D repetitions. The algorithm is efficient and straightforward, with runtime O ( n 2 log ⁡ n + ρ ), where n 2 is the size of the input array and ρ is the number of maximal 2D repetitions in the output.

Details DOI

TCS Journal 2018 Journal Article

Period recovery of strings over the Hamming and edit distances

  • Amihood Amir
  • Mika Amit
  • Gad M. Landau
  • Dina Sokol

A string T of length m is periodic in P of length p if P is a substring of T and T [ i ] = T [ i + p ] for all 0 ≤ i ≤ m − p − 1 and m ≥ 2 p. The shortest such prefix, P, is called the period of T (i. e. , P = T [ 0. . p − 1 ] ). In this paper we investigate the period recovery problem. Given a string S of length n, find the primitive period(s) P such that the distance between S and a string T that is periodic in P is below a threshold τ. We consider the period recovery problem over both the Hamming distance and the edit distance. For the Hamming distance case, we present an O ( n log ⁡ n ) -time algorithm, where τ is given as ⌊ n ( 2 + ϵ ) p ⌋, for ϵ > 0. For the edit distance case, τ = ⌊ n ( 3. 75 + ϵ ) p ⌋ and ϵ > 0, we provide an O ( n 4 / 3 ) -time algorithm.

Details DOI

TCS Journal 2017 Journal Article

String cadences

  • Amihood Amir
  • Alberto Apostolico
  • Travis Gagie
  • Gad M. Landau

Cadences are syntactic regularities in strings, of the family of periods, squares, and repetitions. We say a string has a cadence if a certain character is repeated at regular intervals, possibly with intervening occurrences of that character. We call the cadence anchored if the first interval must be the same length as the others. Although cadences' combinatorial properties have been explored, little work was done regarding the efficiency of their discovery. Recently, implementations involving cadences appeared in works on phylogenetic reconstruction, periodic subgraph mining, and monitoring events in computer networks. In this paper we begin a systematic study of the efficiency of finding cadences. We first give some basic definitions; we then give a sub-quadratic algorithm for determining whether a string has any cadence consisting of at least three occurrences of a character, and a nearly linear algorithm for finding all anchored cadences; finally, we propose a data structure that captures many features of cadences and allows for the efficient detection of many types of cadences. In particular, all sub-cadences can be detected and reported in time proportional to the sum of their lengths.

Details DOI

TCS Journal 2016 Journal Article

Algorithms for Jumbled Indexing, Jumbled Border and Jumbled Square on run-length encoded strings

  • Amihood Amir
  • Alberto Apostolico
  • Tirza Hirst
  • Gad M. Landau
  • Noa Lewenstein
  • Liat Rozenberg

In this paper we investigate jumbled (Abelian) versions of three classical strings problems. In all these problems we assume the input string S [ 1. . n ] is given in its run-length format S ′ [ 1. . r ]. The Jumbled Indexing problem is the problem of indexing a string S ′ [ 1. . r ] over | Σ | for histogram queries, i. e. given a pattern P, we want to find all substrings of S that are permutations of P. We provide an algorithm that constructs an index of size O ( r 2 | Σ | ) in time O ( r 2 ( log ⁡ r + | Σ | log ⁡ | Σ | ) ), which allows answering histogram queries in O ( | Σ | 3 log ⁡ r ) -time. The Jumbled Border problem is the problem of finding for every location j in S, the longest proper prefix of S [ 1. . j ] that is also a permutation of a proper suffix of S [ 1. . j ], if such exists. We provide an algorithm that solves this problem in O ( | Σ | ( r 2 + n ) ) time, and O ( | Σ | n ) space. A Jumbled Square is a string of the form x x ¯, where x ¯ is a permutation of x. The Jumbled Square problem is the problem of finding for every location j in S, the longest jumbled square that ends in j, if such exists. We provide an algorithm that solves this problem in O ( | Σ | ( r 2 + n ) ) time, and O ( | Σ | n ) space.

Details DOI

TCS Journal 2015 Journal Article

A PTAS for the Square Tiling Problem

  • Amihood Amir
  • Alberto Apostolico
  • Gad M. Landau
  • Ely Porat
  • Oren Sar Shalom

The Square Tiling Problem was recently introduced as equivalent to the problem of reconstructing an image from patches and a possible general-purpose indexing tool. Unfortunately, the Square Tiling Problem was shown to be NP -hard. A 1/2-approximation is known. We show that if the tile alphabet is fixed and finite, there is a Polynomial Time Approximation Scheme (PTAS) for the Square Tiling Problem with approximation ratio of ( 1 − ϵ 2 log ⁡ n ) for any given ϵ ≤ 1. Another topic handled in this paper is the NP -hardness of the Tiling problem with an infinite alphabet. We show that when the alphabet is not bounded, even the decision version for rectangles of size 3n is NP -Complete.

Details DOI

I&C Journal 2015 Journal Article

Approximate periodicity

  • Amihood Amir
  • Estrella Eisenberg
  • A. Levy

Finding an approximate period in a given string S of length n is defined as follows. Let S ′ be a periodic string closest to S under some distance metric, find the smallest period of S ′. This period is called an approximate period of S under the given metric. Let the distance between the input string S and a closest periodic string under the Hamming distance S ′ be k. We develop algorithms that construct an approximate period of S under the Hamming distance in time O ( n k log ⁡ log ⁡ n ) and under the swap distance in time O ( n 2 ). Finally, we show an O ( n log ⁡ n ) algorithm for finite alphabets, and an O ( n log 3 ⁡ n ) algorithm for infinite alphabets, that approximate the minimum number of mismatches between the input string and a closest periodic string under the Hamming distance.

Details DOI

TCS Journal 2015 Journal Article

Dictionary matching with a few gaps

  • Amihood Amir
  • Avivit Levy
  • Ely Porat
  • B. Riva Shalom

The dictionary matching with gaps problem is to preprocess a dictionary D of total size | D | containing d gapped patterns P 1, …, P d over an alphabet Σ, where each gapped pattern P i is a sequence of subpatterns separated by bounded sequences of don't cares. Then, given a query text T of length n over Σ, the goal is to output all locations in T in which a pattern P i ∈ D, 1 ≤ i ≤ d, ends. There is a renewed current interest in the gapped matching problem stemming from cyber security. In this paper we solve the problem where all patterns in the dictionary have one gap or a few gaps with at least α and at most β don't cares, where α and β are given parameters. Specifically, we show that the dictionary matching with a single gap problem can be solved in either O ( d log ⁡ d + | D | ) preprocessing time and O ( d log ε ⁡ d + | D | ) space, and query time O ( n ( β − α ) log ⁡ log ⁡ d log 2 ⁡ | D | + occ ), where occ is the number of patterns found, or preprocessing time and space: O ( d 2 + | D | ), and query time O ( n ( β − α ) + occ ), where occ is the number of patterns found. We also show that the dictionary matching with k gaps problem, where k ≥ 1, can be solved in preprocessing time: O ( | D | log ⁡ | D | ), space: O ( | D | + d ( c 1 log ⁡ d ) k k! ), and query time: O ( ( β − α ) k ( n + ( c 2 log ⁡ d ) k k! log ⁡ log ⁡ | D | ) + occ ), where c 1, c 2 > 1 are constants and occ is the number of patterns found. As far as we know, these are the best solutions for this setting of the problem, where many overlaps may exist in the dictionary.

Details DOI

TCS Journal 2014 Journal Article

Closest periodic vectors in L p spaces

  • Amihood Amir
  • Estrella Eisenberg
  • Avivit Levy
  • Noa Lewenstein

The problem of finding the period of a vector V is central to many applications. Let V ′ be a periodic vector closest to V under some metric. We seek this V ′, or more precisely we seek the smallest period that generates V ′. In this paper we consider the problem of finding the closest periodic vector in L p spaces. The measures of “closeness” that we consider are the metrics in the different L p spaces. Specifically, we consider the L 1, L 2 and L ∞ metrics. In particular, for a given n-dimensional vector V, we develop O ( n 2 ) time algorithms (a different algorithm for each metric) that construct the smallest period that defines such a periodic n-dimensional vector V ′. We call that vector the closest periodic vector of V under the appropriate metric. We also show (three) O ˜ ( n ) time constant approximation algorithms for the period of the approximate closest periodic vector.

Details DOI

TCS Journal 2014 Journal Article

Detecting approximate periodic patterns

  • Amihood Amir
  • Alberto Apostolico
  • Estrella Eisenberg
  • Gad M. Landau
  • Avivit Levy
  • Noa Lewenstein

Given ϵ ∈ [ 0, 1 ), the ϵ-Relative Error Periodic Pattern Problem (REPP) is the following: INPUT: An n-long sequence S of numbers s i ∈ N in increasing order. OUTPUT: The longest ϵ-relative error periodic pattern, i. e. , the longest subsequence s i 1, s i 2, …, s i k of S, for which there exists a number p such that the absolute difference between any two consecutive numbers in the subsequence is at least p and at most p ( 1 + ϵ ). The best known algorithm for this problem has O ( n 3 ) time complexity. This bound is too high for large inputs in practice. In this paper we give a new algorithm for finding the longest ϵ-relative error periodic pattern (the REPP problem). Our method is based on a transformation of the input sequence into a different representation: the ϵ-active maximal intervals list L, defined in this paper. We show that the transformation of S to the list L can be done efficiently (quadratic in n and linear in the size of L) and prove that our algorithm is linear in the size of L. This enables us to prove that our algorithm works in sub-cubic time on inputs for which the best known algorithm works in O ( n 3 ) time. Moreover, though it may happen that our algorithm would still be cubic, it is never worse than the known O ( n 3 ) -algorithm and in many situations its complexity is O ( n 2 ) time.

Details DOI

I&C Journal 2012 Journal Article

Combinatorial Pattern Matching (CPM 2010)

  • Amihood Amir
  • Laxmi Parida

Combinatorial Pattern Matching (CPM) addresses issues of searching and matching strings and more complicated structures such as trees, regular expressions, graphs, point sets, and arrays, in various formats. The goal is to derive non-trivial combinatorial properties of such structures and exploit these properties in order to achieve superior performance for the corresponding computational problems. However, another important goal is to analyze and pinpoint the properties and conditions under which searches cannot be performed efficiently. Over the past few decades a steady flow of high-quality research on this subject has changed a sparse set of isolated results into a full-fledged area of algorithmics. This area is continuing to grow even further due to the increasing demand for speed and efficiency that stems from important applications such as the World Wide Web, computational biology, computer vision, and multimedia systems. These involve requirements for information retrieval in heterogeneous databases, data compression and pattern recognition. The field has produced a large number of excellent new researchers, books, and conferences. One of the first conferences in the area was the Combinatorial Pattern Matching (CPM) conference. The objective of the annual CPM gathering is to provide an international forum for research in combinatorial pattern matching and related applications. The first twenty one meetings were held in Paris, London, Tucson, Padova, Asilomar, Helsinki, Laguna Beach, Aarhus, Piscataway, Warwick, Montreal, Jerusalem, Fukuka, Morelia, Istanbul, Jeju Island, Barcelona, London (Ontario), Pisa, Lille, Brooklyn, and Palermo over the years 1990–2011. After the first meeting, a selection of papers appeared as a special issue of Theoretical Computer Science in volume 92. The proceedings of the third to twenty first meetings appeared in the Springer LNCS series. The general organization and orientation of the CPM conferences is coordinated by a steering committee composed of Alberto Apostolico, Maxime Crochemore, and Zvi Galil. The papers contained in this volume were chosen from the abstracts presented at the 20th Annual Symposium on Combinatorial Pattern Matching, held June 21–23, 2010 at NYU-Poly in Brooklyn, New York. The conference was supported by NYU-Poly, The Center for Advanced Technology in Telecommunication (CATT) and IBM Research. Twenty eight extended abstracts were chosen after a refereeing process, and three presentations were invited to the conference. Those abstracts appeared in the symposium proceedings Springer LNCS 6129. Authors of the seven best ranked conference papers were invited to submit their papers to this special issue of Information and Computation. The papers went through a thorough review and the results appear in this volume.

Details DOI

TCS Journal 2012 Journal Article

Quasi-distinct parsing and optimal compression methods

  • Amihood Amir
  • Yonatan Aumann
  • Avivit Levy
  • Yuri Roshko

In this paper, the optimality proof of Ziv–Lempel coding is re-studied, and a more general compression optimality theorem is derived. In particular, the property of quasi-distinct parsing is defined. This property allows infinitely many repetitions of phrases in the parsing as long as the total number of repetitions is o ( n / log n ), where n is length of the parsed string. The quasi-distinct parsing property is weaker than distinct parsing used in the original proof which does not allow repetitions of phrases in the parsing. Yet we show that the theorem holds with this weaker property as well. This provides a better understanding of the optimality proof of Ziv–Lempel coding, together with a new tool for proving optimality of other compression schemes which is applicable for a much wider family of codes. To demonstrate the possible use of this generalization, a new coding method–the Arithmetic Progression Tree coding (APT)–is presented. This new coding method is based on a principle that is very different from Ziv–Lempel’s coding. Nevertheless, the APT coding is analyzed in this paper and using the generalized theorem shown to be asymptotically optimal up to a constant factor, 1 1 Of course, a constant factor for a compression method may indicate that the method is practically useless. In the APT proof presented in this paper the constant is less than 10, however, this constant may be only a byproduct of an inefficiency of the proof. The true constant may be much less. if the APT quasi-distinctness hypothesis holds. An empirical evidence that this hypothesis holds is also given.

Details DOI

TCS Journal 2011 Journal Article

Approximate string matching with stuck address bits

  • Amihood Amir
  • Estrella Eisenberg
  • Orgad Keller
  • Avivit Levy
  • Ely Porat

A string S ∈ Σ m can be viewed as a set of pairs { ( s i, i ) ∣ s i ∈ S, i ∈ { 0, …, m − 1 } }. We follow the recent work on pattern matching with address errors and consider approximate pattern matching problems arising from the setting where errors are introduced to the location component ( i ), rather than the more traditional setting, where errors are introduced to the content itself ( s i ). Specifically, we continue the work on string matching in the presence of address bit errors. In this paper, we consider the case where bits of i may be stuck, either in a consistent or transient manner. We formally define the corresponding approximate pattern matching problems, and provide efficient algorithms for their resolution.

Details DOI

TCS Journal 2011 Journal Article

Efficient algorithms for consensus string problems minimizing both distance sum and radius

  • Amihood Amir
  • Gad M. Landau
  • Joong Chae Na
  • Heejin Park
  • Kunsoo Park
  • Jeong Seop Sim

The consensus (string) problem is finding a representative string, called a consensus, of a given set S of strings. In this paper we deal with consensus problems considering both distance sum and radius, where the distance sum is the sum of (Hamming) distances from the strings in S to the consensus and the radius is the longest (Hamming) distance from the strings in S to the consensus. Although there have been results considering either distance sum or radius, there have been no results considering both, to the best of our knowledge. We present the first algorithms for two consensus problems considering both distance sum and radius for three strings: one problem is to find an optimal consensus minimizing both distance sum and radius. The other problem is to find a bounded consensus such that the distance sum is at most s and the radius is at most r for given constants s and r. Our algorithms are based on characterization of the lower bounds of distance sum and radius, and thus they solve the problems efficiently. Both algorithms run in linear time.

Details DOI

TCS Journal 2009 Journal Article

Approximate string matching with address bit errors

  • Amihood Amir
  • Yonatan Aumann
  • Oren Kapah
  • Avivit Levy
  • Ely Porat

A string S ∈ Σ m can be viewed as a set of pairs S = { ( σ i, i ): i ∈ { 0, …, m − 1 } }. We consider approximate pattern matching problems arising from the setting where errors are introduced to the location component ( i ), rather than the more traditional setting, where errors are introduced into the content itself ( σ i ). In this paper, we consider the case where bits of i may be erroneously flipped, either in a consistent or transient manner. We formally define the corresponding approximate pattern matching problems, and provide efficient algorithms for their resolution, while introducing some novel techniques.

Details DOI

TCS Journal 2009 Journal Article

Efficient computations of ℓ 1 and ℓ ∞ rearrangement distances

  • Amihood Amir
  • Yonatan Aumann
  • Piotr Indyk
  • Avivit Levy
  • Ely Porat

Recently, a new pattern matching paradigm was proposed, pattern matching with address errors. In this paradigm approximate string matching problems are studied, where the content is unaltered and only the locations of the different entries may change. Specifically, a broad class of problems was defined—the class of rearrangement errors. In this type of error the pattern is transformed through a sequence of rearrangement operations, each with an associated cost. The natural ℓ 1 and ℓ 2 rearrangement systems were considered. The best algorithm presented for general patterns, that may have repeating symbols, is O ( n m ). In this paper, we show that the problem can be approximated in linear time for general patterns! Another natural rearrangement system is considered in this paper—the ℓ ∞ rearrangement distance. For this new rearrangement system efficient exact solutions for different variants of the problem are provided, as well as a faster approximation.

Details DOI

TCS Journal 2008 Journal Article

Computing similarity of run-length encoded strings with affine gap penalty

  • Jin Wook Kim
  • Amihood Amir
  • Gad M. Landau
  • Kunsoo Park

The problem of computing the similarity of two run-length encoded strings has been studied for various scoring metrics. Many algorithms have been developed for the longest common subsequence metric and some algorithms for the Levenshtein distance metric and the weighted edit distance metric. In this paper we consider similarity based on the affine gap penalty metric which is a more general and rather complicated scoring metric than the weighted edit distance. To compute the similarity in this model efficiently, we convert the problem into a path problem on a directed acyclic graph and use some properties of maximum paths in this graph. We present an O ( n m ′ + n ′ m ) time algorithm for computing the similarity of two run-length encoded strings in the affine gap penalty model, where n and m are the lengths of given two strings whose run-length encoded lengths are n ′ and m ′, respectively.

Details DOI

TCS Journal 2008 Journal Article

Generalized LCS

  • Amihood Amir
  • Tzvika Hartman
  • Oren Kapah
  • B. Riva Shalom
  • Dekel Tsur

The Longest Common Subsequence (LCS) is a well studied problem, having a wide range of implementations. Its motivation is in comparing strings. It has long been of interest to devise a similar measure for comparing higher dimensional objects, and more complex structures. In this paper we study the Longest Common Substructure of two matrices and show that this problem is N P -hard. We also study the Longest Common Subforest problem for multiple trees including a constrained version, as well. We show N P -hardness for k > 2 unordered trees in the constrained LCS. We also give polynomial time algorithms for ordered trees and prove a lower bound for any decomposition strategy for k trees.

Details DOI

TCS Journal 2008 Journal Article

Property matching and weighted matching

  • Amihood Amir
  • Eran Chencinski
  • Costas Iliopoulos
  • Tsvi Kopelowitz
  • Hui Zhang

In many pattern matching applications the text has some properties attached to its various parts. Pattern Matching with Properties (Property Matching, for short), involves a string matching between the pattern and the text, and the requirement that the text part satisfies some property. Some immediate examples come from molecular biology where it has long been a practice to consider special areas in the genome by their structures. It is straightforward to do sequential matching in a text with properties. However, indexing in a text with properties becomes difficult if we desire the time to be output dependent. We present an algorithm for indexing a text with properties in O ( n log | Σ | + n log log n ) time for preprocessing and O ( | P | log | Σ | + tocc π ) per query, where n is the length of the text, P is the sought pattern, Σ is the alphabet, and tocc π is the number of occurrences of the pattern that satisfy some property π. As a practical use of Property Matching we show how to solve Weighted Matching problems using techniques from Property Matching. Weighted sequences have recently been introduced as a tool to handle a set of sequences that are not identical but have many local similarities. The weighted sequence is a “statistical image” of this set, where we are given the probability of every symbol’s occurrence at every text location. Weighted matching problems are pattern matching problems where the given text is weighted. We present a reduction from Weighted Matching to Property Matching that allows off-the-shelf solutions to numerous weighted matching problems including indexing, swapped matching, parameterized matching, approximate matching, and many more. Assuming that one seeks the occurrence of pattern P with probability ϵ in weighted text T of length n, we reduce the problem to a property matching problem of pattern P in text T ′ of length O ( n ( 1 ϵ ) 2 log 1 ϵ ).

Details DOI

TCS Journal 2006 Journal Article

Faster two-dimensional pattern matching with rotations

  • Amihood Amir
  • Oren Kapah
  • Dekel Tsur

The most efficient currently known algorithms for two-dimensional pattern matching with rotations have a worst case time complexity of O ( n 2 m 3 ), where the size of the text is n × n and the size of the pattern is m × m. In this paper we present a new algorithm for the problem whose running time is O ( n 2 m 2 ).

Details DOI

I&C Journal 2004 Journal Article

The submatrices character count problem: an efficient solution using separable values

  • Amihood Amir
  • Kenneth W. Church
  • Emanuel Dar

The subsequence character count problem has as its input an array S=S[1], …, S[n] of symbols over alphabet Σ and a natural number m. Its output is: for every i, i=1, …, n−m+1, the number of different alphabet symbols occurring in the subsequence S[i], S[i+1], …, S[i+m−1]. The subsequence character count problem is a natural problem that has many uses. It can be solved in linear time for finite alphabets and in time O(nlogm) for infinite alphabets. When the character count problem is generalized to two dimensions it becomes the submatrix character count problem. Its input is an n×n matrix T over alphabet Σ and a natural number m. Its output is: for every i, j, i, j=1, …, n−m+1, the number of different alphabet symbols occurring in the submatrix T[i+k, j+ℓ], k=0, …, m−1; ℓ=0, …, m−1. The straightforward one-dimensional solution slides a window along the text adding an element and deleting an element at every step. The problem with two dimensions is that at every move of the window there are m elements added and m deleted. In this paper, we present an alternate one-dimensional solution that generalizes to two dimensions. We achieve a O(n 2) time solution to the submatrix character count problem over a finite alphabet and a O(n 2logm) solution over an infinite alphabet.

Details DOI

TCS Journal 2004 Journal Article

Two-dimensional pattern matching with rotations

  • Amihood Amir
  • Ayelet Butman
  • Maxime Crochemore
  • Gad M. Landau
  • Mary Schaps

The problem of pattern matching with rotation is that of finding all occurrences of a two-dimensional pattern in a text, in all possible rotations. We prove an upper and lower bound on the number of such different possible rotated patterns. Subsequently, given an m×m array (pattern) and an n×n array (text) over some finite alphabet Σ, we present a new method yielding an O(n 2 m 3) time algorithm for this problem.

Details DOI

TCS Journal 2003 Journal Article

Inplace run-length 2d compressed search

  • Amihood Amir
  • Gad M. Landau
  • Dina Sokol

The recent explosion in the amount of stored data has necessitated the storage and transmission of data in compressed form. The need to quickly access this data has given rise to a new paradigm in searching, that of compressed matching (Proc. Data Compression Conf. , Snow Bird, UT, 1992, pp. 279–288; Proc. 8th Annu. Symp. on Combinatorial Pattern Matching (CPM 97), Lecture Notes in Computer Science, Vol. 1264, Springer, Berlin, 1997, pp. 40–51; Proc. 7th Annu. Symp. on Combinatorial Pattern Matching (CPM 96), Lecture Notes in Computer Science, Vol. 1075, Springer, Berlin, 1996, pp. 39–49). The goal of the compressed pattern matching problem is to find a pattern in a text without decompressing the text. The criterion of extra space is very relevant to compressed searching. An algorithm is called inplace if the amount of extra space used is proportional to the input size of the pattern. In this paper we present a 2d compressed matching algorithm that is inplace. Let compressed(T) and compressed(P) denote the compressed text and pattern, respectively. The algorithm presented in this paper runs in time O(|compressed(T)|+|P|log σ) where σ is min(|P|, |Σ|), and Σ is the alphabet, for all patterns that have no trivial rows (rows consisting of a single repeating symbol). The amount of space used is O(|compressed(P)|). The compression used is the 2d run-length compression, used in FAX transmission.

Details DOI

I&C Journal 2003 Journal Article

Overlap matching

  • Amihood Amir
  • Richard Cole
  • Ramesh Hariharan
  • Moshe Lewenstein
  • Ely Porat

We propose a new paradigm for string matching, namely structural matching. In structural matching, the text and pattern contents are not important. Rather, some areas in the text and pattern, such as intervals, are singled out. A “match” is a text location where a specified relation between the text and pattern areas is satisfied. In particular we define the structural matching problem of overlap (parity) matching. We seek the text locations where all overlaps of the given pattern and text intervals have even length. We show that this problem can be solved in time O(nlogm), where the text length is n and the pattern length is m. As an application of overlap matching, we show how to reduce the string matching with swaps problem to the overlap matching problem. The string matching with swaps problem is the problem of string matching in the presence of local swaps. The best deterministic upper bound known for this problem was O(nm 1/3logmlogσ) for a general alphabet Σ, where σ=min(m, |Σ|). Our reduction provides a solution to the pattern matching with swaps problem in time O(nlogmlogσ).

Details DOI

I&C Journal 2003 Journal Article

Some connections between bounded query classes and non-uniform complexity

  • Amihood Amir
  • Richard Beigel
  • William Gasarch

Let A(x) be the characteristic function of A. Consider the function C A k (x 1, …, x k )=A(x 1)⋯A(x k ). We show that if C A k can be computed in polynomial time with fewer than k queries to some set X then A∈P/poly. A generalization of this result has applications to bounded query classes, circuits, and enumerability. In particular we obtain the following. (1) Assuming Σ3 p ≠Π3 p, there are functions computable using f(n)+1 queries to SAT that are not computable using f(n) queries to SAT, for f(n)=O(logn). (2) If C A k, restricted to length n inputs, can be computed by an unbounded fanin oracle circuit of size s(n) and depth d(n), with k−1 queries to some set X, then A can be computed with an unbounded fanin (non-oracle) circuit of size n O(k) s(n) and depth d(n)+O(1). (3) Assuming that PH≠Σ4 p ∩Π4 p, and ϵ<1, #SAT is not 2 n ϵ -enumerable.

Details DOI

I&C Journal 1998 Journal Article

Optimal Parallel Two Dimensional Text Searching on a CREW PRAM

  • Amihood Amir
  • Gary Benson
  • Martin Farach-Colton

We present a parallel algorithm for two dimensional text searching over a general alphabet. This algorithm is optimal in two ways. First, the total number of operations on the text is linear. Second, the algorithm takes timeO(log m) on a CREW PRAM (wheremis the length of the longest dimension of the pattern), thus matching the lower bound for string matching on a PRAM without concurrent writes. On a CRCW, the algorithm runs in timeO(loglog m).

Details DOI

FOCS Conference 1997 Conference Paper

Pattern Matching with Swaps

  • Amihood Amir
  • Yonatan Aumann
  • Gad M. Landau
  • Moshe Lewenstein
  • Noa Lewenstein

Let a text string T of n symbols and a pattern string P of m symbols from alphabet /spl Sigma/ be given. A swapped version T' of T is a length n string derived from T by a series of local swaps, (i. e. t/sup '//sub l//spl larr/t/sub l+1/ and t'/sub l+1//spl larr/t/sub l/) where each element can participate in no more than one swap. The Pattern Matching with Swaps problem is that of finding all locations i for which there exists a swapped version T' of T where there is an exact matching of P in location i of T'. It has been an open problem whether swapped matching can be done in less than O(mn) time. In this paper we show the first algorithm that solves the pattern matching with swaps problem in time O(mn). We present an algorithm whose time complexity is O(nm/sup 1/3/ log m log/sup 2/ /spl sigma/) for a general alphabet /spl Sigma/, where /spl sigma/=min(m, |/spl Sigma/|).

Details

FOCS Conference 1994 Conference Paper

Maximum Agreement Subtree in a Set of Evolutionary Trees-Metrics and Efficient Algorithms

  • Dmitry Keselman
  • Amihood Amir

In this paper we prove that the maximum homeomorphic agreement subtree problem is /spl Nscr//spl Pscr/-complete for three trees with unbounded degrees. We then show an approximation algorithm of time O(kn/sup 5/) for choosing the species that are not in a maximum agreement subtree of a set of k trees. Our approximation is guaranteed to provide a set that is no more than 4 times the optimum solution. While the set of evolutionary trees may be large in practice, the trees usually have very small degrees, typically no larger than three. We develop a new method for finding a maximum agreement subtree of k trees, of which one has degree bounded by d. This new method enables us to find a maximum agreement subtree in time O(kn/sup d+1/). >

Details

FOCS Conference 1991 Conference Paper

Adaptive Dictionary Matching

  • Amihood Amir
  • Martín Farach-Colton

Semiadaptive and fully adaptive dictionary matching algorithms are presented. In the fully adaptive algorithm, the dictionary is processed in time O( mod D mod log mod D mod ). Inserting a new pattern P/sub k+1/ into the dictionary can be done in time O mod P/sub K+1/ mod log mod D mod ). A dictionary pattern can be deleted in time O(log mod D mod ). Text scanning is accomplished in time O( mod T mod log mod D mod ). Also presented is a parallel version of the algorithm with optimal speedup for the dictionary construction and pattern addition phase and a logarithmic overhead in the text scan phase. The method used incorporates a new way of using suffix trees as well as a new data structure in which the suffix tree is embedded for the sequential algorithm. >

Details

TCS Journal 1991 Journal Article

Fast parallel and serial multidimensional approximate array matching

  • Amihood Amir
  • Gad M. Landau

Consider the multidimensional array matching problem, where differences between characters of the pattern and characters of the text are permitted. A difference may be due to a mismatch between a text and pattern character, superfluous text character or superfluous pattern character. Given a d-dimensional array of size n d (text) and a d-dimensional array of size m d pattern we present the following algorithms: For a given k, find all occurrences of the pattern in the text with at most k differences. Our serial algorithm runs in time O(n d (dk+k 2)) and the parallel algorithm runs in time O(d( d log n+ k)+k 2) using n d processors. If superfluous characters are not allowed and the only permitted errors are mismatches, we solve the problem serially in time O(n d dk) and in parallel in time O(d( d logn+k)) using n d processors. We present an alternate algorithm for the mismatches problem which runs serially in time O(2 d n d log2 m) and in parallel in time O(d log n) using n d processors. This algorithm is more efficient for large k. We also give an efficient solution to the close-match problem. Here a mismatch weight function f: Σ×Σ→[0, 1] is assigned. The weight function gives weight to the mismatches, some mismatches being worse than others. We present a serial algorithm for finding all appearances of the pattern in the text with a bounded total error in time O(2 d n d log2 m). Our parallel algorithm is again of time complexity O(d log n) using n d processors.

Details DOI

I&C Journal 1988 Journal Article

Polynomial terse sets

  • Amihood Amir
  • William I. Gasarch

Let A be a set and k ∈ N be such that we wish to know the answers to x 1 ∈ A? , x 2 ∈ A? , …, x k ∈ A? for various k-tuples 〈x 1, x 2, …, x k 〉. If this problem requires k queries to A in order to be solved in polynomial time then A is called polynomial terse or pterse. We show the existence of both arbitrarily complex pterse and non-pterse sets; and that P ≠ NP iff every NP-complete set is pterse. We also show connections with p-immunity, p-selective, p-generic sets, and the boolean hierarchy. In our framework unique satisfiability (and a variation of it called kSAT is, in some sense, “close” to satisfiability.

Details DOI

I&C Journal 1987 Journal Article

Preservation of expressive completeness in temporal models

  • Amihood Amir
  • Dov M. Gabbay

A propositional logic is expressively complete if there is a finite set of connectives which define all truth tables. Kamp (1968, Ph. D. thesis, University of California at Los Angeles), Stavi (1979, unpublished manuscript, Bar-Ilan University, Ramat-Gan, Israel), and Gabbay (1976, “Investigations in Modal and Tense Logics”, Reidel, Dordrecht) proved that all Tense Logics over linear time are expressively complete. Here, a constructive method is given to generate time structure whose tense logic is expressively complete from such given models. As a result examples of constructed nonlinear time models yielding functional completeness are also given.

Details DOI
v2026.09.13