Paper

The periodicity lemma is a widely useful result about word combinatorics. Yet, the paper that if often cited as the source for its proof, Uniqueness Theorems for Periodic Functions, uses very unusual techniques in stringology. If a word \(w\) has periods \(p\) and \(q\), and is of length at least \(p+q-\gcd(p, q)\), then \(w\) has period \(\gcd(p,q)\). Before proving this stronger version of the lemma, let us state a weaker version. The point is that this alternative version has a purely combinatorics proof, that is also interesting per se. ...

Regular pattern matching is comes up very often, both in theoretical frameworks and in practice and, as such, is a problem that has been studied a lot. The RAM model in which it is studied, however, does not always take into account the practical difficulties that arise with very large amount of data, which don’t fit in memory. For this reason, it makes sense to study efficient algorithms in a more realistic computational model, the streaming model. ...