Branching Frequency and Markov Entropy of Repetition-Free Languages
From MaRDI portal
Publication:6367012
DOI10.1007/978-3-030-81508-0_27arXiv2105.02750MaRDI QIDQ6367012FDOQ6367012
Authors: Elena A. Petrova, Arseny M. Shur 
Publication date: 6 May 2021
Abstract: We define a new quantitative measure for an arbitrary factorial language: the entropy of a random walk in the prefix tree associated with the language; we call it Markov entropy. We relate Markov entropy to the growth rate of the language and to the parameters of branching of its prefix tree. We show how to compute Markov entropy for a regular language. Finally, we develop a framework for experimental study of Markov entropy by modelling random walks and present the results of experiments with power-free and Abelian-power-free languages.
This page was built for publication: Branching Frequency and Markov Entropy of Repetition-Free Languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6367012)
