arXiv
Open Access
2021
Branching Frequency and Markov Entropy of Repetition-Free Languages
Elena A. Petrova
Arseny M. Shur
Abstrak
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.
Penulis (2)
E
Elena A. Petrova
A
Arseny M. Shur
Akses Cepat
Informasi Jurnal
- Tahun Terbit
- 2021
- Bahasa
- en
- Sumber Database
- arXiv
- Akses
- Open Access ✓