ABSTRACT
Prefix normal words are binary words with the property that no factor has more 1s than the prefix of the same length. Finite prefix normal words were introduced in [Fici and Lipták, DLT 2011]. In this paper, we study infinite prefix normal words and explore their relationship to some known classes of infinite binary words. In particular, we establish a connection between prefix normal words and Sturmian words, between prefix normal words and abelian complexity, and between prefix normality and lexicographic order.
ABSTRACT
Given an ordered set of n items and an unknown subset P of up to p positive elements, we want to identify P by asking the least number of queries 'does Q intersect P?' where Q must consist of consecutive elements. This Interval Group Testing problem arises in the context of splice site detection in genes. We study algorithms that operate in a few stages where queries chosen depending on previous answers, are performed in parallel. We obtain tight bounds for two-stage strategies. Finally, we get results for any number of stages and positives.