Weighted prefix normal words: mind the gap
From MaRDI portal
Publication:832931
DOI10.1007/978-3-030-81508-0_12zbMATH Open1491.68146arXiv2005.09281OpenAlexW3196420219MaRDI QIDQ832931FDOQ832931
Authors: Yannik Eikmeier, Pamela Fleischmann, Mitja Kulczynski, Dirk Nowotka 
Publication date: 25 March 2022
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.
Full work available at URL: https://arxiv.org/abs/2005.09281
Recommendations
- On prefix normal words
- On prefix normal words and prefix normal forms
- On collapsing prefix normal words
- On infinite prefix normal words
- On infinite prefix normal words
- The weighted words collector
- scientific article; zbMATH DE number 5291306
- The method of weighted words revisited
- About prefix sets of words
- On combinatorial generation of prefix normal words
Cites Work
- Abelian complexity of minimal subshifts
- Efficient indexes for jumbled pattern matching with constant-sized alphabet
- Algorithms for jumbled pattern matching in strings
- Clustered Integer 3SUM via Additive Combinatorics
- On hardness of jumbled indexing
- Generalized Pascal triangle for binomial coefficients of words
- Computing abelian complexity of binary uniform morphic words
- Factor versus palindromic complexity of uniformly recurrent infinite words
- A connection between palindromic and factor complexity using return words
- The On-Line Encyclopedia of Integer Sequences
- Another generalization of abelian equivalence: binomial complexity of infinite words
- On growth and fluctuation of \(k\)-abelian complexity
- Cyclic complexity of words
- Computing the \(k\)-binomial complexity of the Thue-Morse word
- The asymptotic number of prefix normal words
- On a class of infinite words with affine factor complexity
- On combinatorial generation of prefix normal words
- On prefix normal words
- On infinite prefix normal words
- On prefix normal words and prefix normal forms
- On collapsing prefix normal words
- Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
- Subword complexity and power avoidance
- Bubble-flip -- a new generation algorithm for prefix normal words
Cited In (4)
Uses Software
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)
