On prefix normal words and prefix normal forms

详细信息    查看全文

• 作者：Pé ; ter Burcsi^a ; ^{bupe@compalg.inf.elte.hu} ; Gabriele Fici^b ; ^{gabriele.fici@unipa.it} ; Zsuzsanna Liptá ; k^c ; ^{zsuzsanna.liptak@univr.it} ; Frank Ruskey^d ; ^{ruskey@cs.uvic.ca} ; Joe Sawada^e ; ^{jsawada@uoguelph.ca}
• 关键词：Prefix normal words ; Prefix normal forms ; Binary languages ; Binary jumbled pattern matching ; Pre-necklaces ; Lyndon words ; Enumeration
• 刊名：Theoretical Computer Science
• 出版年：2017
• 出版时间：10 January 2017
• 年：2017
• 卷：659
• 期：Complete
• 页码：1-13
• 全文大小：450 K
• 卷排序：659

文摘

A 1-prefix normal word is a binary word with the property that no factor has more 1s 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 1s and 0s (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 pnw(n)pnw(n), the number of prefix normal words of length n, showing that, for sufficiently large n,2n−4nlg⁡n≤pnw(n)≤2n−lg⁡n+1.For fixed density (number of 1s), 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 pnw(n)pnw(n), discuss further properties, and state open problems.