Source author record

Péter Burcsi

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 math.CO Formal Languages and Automata Theory

Catalog footprint

Research overview

5works

4topics

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)).

preprint2012arXiv

The method of double chains for largest families with excluded subposets

For a given finite poset $P$ , $La(n,P)$ denotes the largest size of a family $\mathcal{F}$ of subsets of $[n]$ not containing $P$ as a weak subposet. We exactly determine $La(n,P)$ for infinitely many $P$ posets. These posets are built from seven base posets using two operations. For arbitrary posets, an upper bound is given for $La(n,P)$ depending on $|P|$ and the size of the longest chain in $P$ . To prove these theorems we introduce a new method, counting the intersections of $\mathcal{F}$ with double chains, rather than chains.

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.