On prefix normal words and prefix normal forms

Gabriele Fici, Péter Burcsi, Zsuzsanna Lipták, Frank Ruskey, Joe Sawada

Risultato della ricerca: Article

11 Citazioni (Scopus)

Abstract

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), the number of prefix normal words of length n, showing that, for sufficiently large n, 2n−4nlgn≤pnw(n)≤2n−lgn+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), discuss further properties, and state open problems
Lingua originaleEnglish
pagine (da-a)1-13
Numero di pagine13
RivistaTheoretical Computer Science
Volume659
Stato di pubblicazionePublished - 2017

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Entra nei temi di ricerca di 'On prefix normal words and prefix normal forms'. Insieme formano una fingerprint unica.

  • Cita questo

    Fici, G., Burcsi, P., Lipták, Z., Ruskey, F., & Sawada, J. (2017). On prefix normal words and prefix normal forms. Theoretical Computer Science, 659, 1-13.