Prefix frequency of lost positions

DOI10.1016/J.TCS.2017.01.026MaRDI QIDQ2358696zbMATH OpenOpenAlexFDO

Authors Štěpán Holub

Publication date 15 June 2017

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

Lyndon wordsperiodicityruns

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: The concept of "lost positions" is a recently introduced tool for counting the number of runs in words. We investigate the frequency of lost positions in prefixes of words. This leads to an algorithm that allows to show, using an extensive computer search, that the asymptotic density of runs in binary words is less than $183/193approx0.9482$.

Review text

A new and fresh attempt to estimate the number of runs in words over the binary alphabet is presented in this paper. The abstract is easy to follow, however, the author provides additional evidence towards a quick generalized appreciation of the paper's topic. The innovation of the paper is clearly stated. The background theory is fully connected to the given data and the method analysis. Limitations of the proposed method are clearly presented, as well as lemmas and theorems and their corresponding proofs. Tables are presented in an effective manner and are clearly related to the research questions. Data provided support the algorithm's implementation efficiency as well as the conclusions drawn. Different assumptions can lead to various future directions of research on the topic.

Recommendations

• The number of runs in a string
• Not So Many Runs in Strings
• The expected number of runs in a word
• The total run length of a word
• Asymptotic behavior of the numbers of runs and microruns

Cites work

• A Series of Run-Rich Strings
• AN ASYMPTOTIC LOWER BOUND FOR THE MAXIMAL NUMBER OF RUNS IN A STRING
• Asymptotic behavior of the numbers of runs and microruns
• Computing regularities in strings: a survey
• Extracting powers and periods in a word from its runs structure
• Fully bordered words
• How many runs can a string contain?
• scientific article; zbMATH DE number 5717191 (Why is no real title available?)
• scientific article; zbMATH DE number 826052 (Why is no real title available?)
• scientific article; zbMATH DE number 1390079 (Why is no real title available?)
• scientific article; zbMATH DE number 964350 (Why is no real title available?)
• scientific article; zbMATH DE number 3073237 (Why is no real title available?)
• Maximal repetitions in strings
• Repetitions in strings: algorithms and combinatorics
• Square-density increasing mappings
• The ``runs conjecture
• The ``runs theorem
• The number of runs in a string
• Uniqueness Theorems for Periodic Functions

Cited in

(6)

• Lower bounds for the number of repetitions in 2D strings
• Tight Upper Bounds on Distinct Maximal (Sub-)Repetitions in Highly Compressible Strings
• Palindromic periodicities
• Linear time runs over general ordered alphabets
• Clusters of repetition roots: single chains
• Upper bounds on distinct maximal (sub-)repetitions in compressed strings

This page was built for publication: Prefix frequency of lost positions

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