Arrow Research search

Author name cluster

Ayelet Butman

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.

4 papers
2 author rows

Possible papers

4

TCS Journal 2016 Journal Article

Permuted scaled matching

  • Ayelet Butman
  • Noa Lewenstein
  • J. Ian Munro

Scaled matching and permutation matching are two well known paradigms in the domain of pattern matching. Scaled matching refers to finding an occurrence of a pattern which is enlarged proportionally by some scale k within a larger text. Permutation matching is the problem of finding all substrings within a text where the character statistics of the substring and the pattern are the same. Permutation matching is easy, while scaled matching requires innovative solutions. One interesting setting of applications is the merge of the two. The problem of scaled permuted matching (i. e. first permuting and then scaling) has been addressed and solved optimally. However, it was left as an open problem whether there are efficient algorithms for permuted scaled matching. In this paper we solve the problem efficiently in a deterministic setting and optimally in a randomized setting.

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
v2026.09.13