Periods and Borders of Random Words

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10331382" target="_blank" >RIV/00216208:11320/16:10331382 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Periods and Borders of Random Words

Original language description

We investigate the behavior of the periods and border lengths of random words over a fixed alphabet. We show that the asymptotic probability that a random word has a given maximal border length k is a constant, depending only on k and the alphabet size ℓ . We give a recurrence that allows us to determine these constants with any required precision. This also allows us to evaluate the expected period of a random word. For the binary case, the expected period is asymptotically about nMINUS SIGN 1.641 . We also give explicit formulas for the probability that a random word is unbordered or has maximum border length one.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

BA - General mathematics

OECD FORD branch

—

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2016

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Leibniz international proceedings in informatics

ISBN

978-3-95977-001-9

ISSN

1868-8969

e-ISSN

—

Number of pages

10

Pages from-to

1-10

Publisher name

Dagstuhl Publishing

Place of publication

Německo

Event location

USA, Orleans

Event date

Feb 17, 2016

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—