Weighted prefix normal words: mind the gap

DOI10.1007/978-3-030-81508-0_12MaRDI QIDQ832931zbMATH OpenOpenAlexFDO

Authors Yannik Eikmeier, Pamela Fleischmann, Mitja Kulczynski, Dirk Nowotka

Publication date 25 March 2022

Full work available at URL https://arxiv.org/abs/2005.09281

prefix normal word weighted prefix normality

Abstract: A prefix normal word is a binary word whose prefixes contain at least as many 1s as any of its factors of the same length. Introduced by Fici and Lipt'ak in 2011 the notion of prefix normality is so far only defined for words over the binary alphabet. In this work we investigate a generalisation for finite words over arbitrary finite alphabets, namely weighted prefix normality. We prove that weighted prefix normality is more expressive than binary prefix normality. Furthermore, we investigate the existence of a weighted prefix normal form since weighted prefix normality comes with several new peculiarities that did not already occur in the binary case. We characterise these issues and finally present a standard technique to obtain a generalised prefix normal form for all words overarbitrary, finite alphabets.

Review text

The authors discuss possible generalizations to larger alphabets of the notion of prefix normal words defined by \textit{G. Fici} and \textit{Z. Lipták} [Lect. Notes Comput. Sci. 6795, 228--238 (2011; Zbl 1221.68128)] as words whose prefixes contain at least as many 1s as any of their factors of the same length. The suggestion is to assign to each letter of the alphabet its weight and to consider, instead of the number of ones, the weight function defined either as the sum or the product of weights of letters. The situations can be predictably different and rather complicated depending on the details of the definition of the weight function. As is announced in the paper, the properties of the weight function are nicer when it is \textit{gapfree}. For the entire collection see [Zbl 1482.68035].

Recommendations

Cites work

Cited in

(6)

Describes a project that uses

Uses Software

OEIS

This page was built for publication: Weighted prefix normal words: mind the gap

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q832931)