Source author record

Zsuzsanna Lipták

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Discrete Mathematics Formal Languages and Automata Theory math.CO Information Retrieval

Catalog footprint

Research overview

7works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

On Prefix Normal Words and Prefix Normal Forms

A $1$ -prefix normal word is a binary word with the property that no factor has more $1$ s than the prefix of the same length; a $0$ -prefix normal word is defined analogously. These words arise in the context of indexed binary jumbled pattern matching, where the aim is to decide whether a word has a factor with a given number of $1$ s and $0$ s (a given Parikh vector). Each binary word has an associated set of Parikh vectors of the factors of the word. Using prefix normal words, we provide a characterization of the equivalence class of binary words having the same set of Parikh vectors of their factors. We prove that the language of prefix normal words is not context-free and is strictly contained in the language of pre-necklaces, which are prefixes of powers of Lyndon words. We give enumeration results on $\textit{pnw}(n)$ , the number of prefix normal words of length $n$ , showing that, for sufficiently large $n$ , $2^{n-4 \sqrt{n \lg n}} \le \textit{pnw}(n) \le 2^{n - \lg n + 1}.$ For fixed density (number of $1$ s), we show that the ordinary generating function of the number of prefix normal words of length $n$ and density $d$ is a rational function. Finally, we give experimental results on $\textit{pnw}(n)$ , discuss further properties, and state open problems.

preprint2014arXiv

Normal, Abby Normal, Prefix Normal

A prefix normal word is a binary word with the property that no substring has more 1s than the prefix of the same length. This class of words is important in the context of binary jumbled pattern matching. In this paper we present results about the number $pnw(n)$ of prefix normal words of length $n$ , showing that $pnw(n) =Ω\left(2^{n - c\sqrt{n\ln n}}\right)$ for some $c$ and $pnw(n) = O \left(\frac{2^n (\ln n)^2}{n}\right)$ . We introduce efficient algorithms for testing the prefix normal property and a "mechanical algorithm" for computing prefix normal forms. We also include games which can be played with prefix normal words. In these games Alice wishes to stay normal but Bob wants to drive her "abnormal" -- we discuss which parameter settings allow Alice to succeed.

preprint2014arXiv

On Combinatorial Generation of Prefix Normal Words

A prefix normal word is a binary word with the property that no substring has more 1s than the prefix of the same length. This class of words is important in the context of binary jumbled pattern matching. In this paper we present an efficient algorithm for exhaustively listing the prefix normal words with a fixed length. The algorithm is based on the fact that the language of prefix normal words is a bubble language, a class of binary languages with the property that, for any word w in the language, exchanging the first occurrence of 01 by 10 in w results in another word in the language. We prove that each prefix normal word is produced in O(n) amortized time, and conjecture, based on experimental evidence, that the true amortized running time is O(polylog(n)).

preprint2014arXiv

On the Number of Closed Factors in a Word

A closed word (a.k.a. periodic-like word or complete first return) is a word whose longest border does not have internal occurrences, or, equivalently, whose longest repeated prefix is not right special. We investigate the structure of closed factors of words. We show that a word of length $n$ contains at least $n+1$ distinct closed factors, and characterize those words having exactly $n+1$ closed factors. Furthermore, we show that a word of length $n$ can contain $Θ(n^{2})$ many distinct closed factors.

preprint2013arXiv

Binary Jumbled String Matching for Highly Run-Length Compressible Texts

The Binary Jumbled String Matching problem is defined as: Given a string $s$ over $\{a,b\}$ of length $n$ and a query $(x,y)$ , with $x,y$ non-negative integers, decide whether $s$ has a substring $t$ with exactly $x$ $a$ 's and $y$ $b$ 's. Previous solutions created an index of size O(n) in a pre-processing step, which was then used to answer queries in constant time. The fastest algorithms for construction of this index have running time $O(n^2/\log n)$ [Burcsi et al., FUN 2010; Moosa and Rahman, IPL 2010], or $O(n^2/\log^2 n)$ in the word-RAM model [Moosa and Rahman, JDA 2012]. We propose an index constructed directly from the run-length encoding of $s$ . The construction time of our index is $O(n+ρ^2\log ρ)$ , where O(n) is the time for computing the run-length encoding of $s$ and $ρ$ is the length of this encoding---this is no worse than previous solutions if $ρ= O(n/\log n)$ and better if $ρ= o(n/\log n)$ . Our index $L$ can be queried in $O(\log ρ)$ time. While $|L|= O(\min(n, ρ^{2}))$ in the worst case, preliminary investigations have indicated that $|L|$ may often be close to $ρ$ . Furthermore, the algorithm for constructing the index is conceptually simple and easy to implement. In an attempt to shed light on the structure and size of our index, we characterize it in terms of the prefix normal forms of $s$ introduced in [Fici and Lipták, DLT 2011].

preprint2013arXiv

Indexes for Jumbled Pattern Matching in Strings, Trees and Graphs

We consider how to index strings, trees and graphs for jumbled pattern matching when we are asked to return a match if one exists. For example, we show how, given a tree containing two colours, we can build a quadratic-space index with which we can find a match in time proportional to the size of the match. We also show how we need only linear space if we are content with approximate matches.

preprint2011arXiv

Algorithms for Jumbled Pattern Matching in Strings

The Parikh vector p(s) of a string s is defined as the vector of multiplicities of the characters. Parikh vector q occurs in s if s has a substring t with p(t)=q. We present two novel algorithms for searching for a query q in a text s. One solves the decision problem over a binary text in constant time, using a linear size index of the text. The second algorithm, for a general finite alphabet, finds all occurrences of a given Parikh vector q and has sub-linear expected time complexity; we present two variants, which both use a linear size index of the text.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Zsuzsanna Lipták

Research overview

Is this your work?

7 publications

On Prefix Normal Words and Prefix Normal Forms

Normal, Abby Normal, Prefix Normal

On Combinatorial Generation of Prefix Normal Words

On the Number of Closed Factors in a Word

Binary Jumbled String Matching for Highly Run-Length Compressible Texts

Indexes for Jumbled Pattern Matching in Strings, Trees and Graphs

Algorithms for Jumbled Pattern Matching in Strings

See the researcher in context

Building this map preview