Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/111364
Title: Branching Frequency and Markov Entropy of Repetition-Free Languages
Authors: Petrova, E. A.
Shur, A. M.
Issue Date: 2021
Publisher: Springer Science and Business Media Deutschland GmbH
Springer International Publishing
Citation: Petrova E. A. Branching Frequency and Markov Entropy of Repetition-Free Languages / E. A. Petrova, A. M. Shur. — DOI 10.21638/spbu15.2021.308 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2021. — Vol. 12811 LNCS. — P. 328-341.
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 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. © 2021, Springer Nature Switzerland AG.
Keywords: ABELIAN-POWER-FREE LANGUAGE
MARKOV ENTROPY
POWER-FREE LANGUAGE
PREFIX TREE
RANDOM WALK
ENTROPY
FORESTRY
RANDOM PROCESSES
FACTORIAL LANGUAGES
FREE LANGUAGES
PREFIX TREES
QUANTITATIVE MEASURES
RANDOM WALK
MODELING LANGUAGES
URI: http://hdl.handle.net/10995/111364
Access: info:eu-repo/semantics/openAccess
Conference name: 25th International Conference on Developments in Language Theory, DLT 2021
Conference date: 16 August 2021 through 20 August 2021
SCOPUS ID: 85113192800
PURE ID: 22983763
ISSN: 0302-9743
ISBN: 9783030815073
DOI: 10.21638/spbu15.2021.308
metadata.dc.description.sponsorship: Supported by the Ministry of Science and Higher Education of the Russian Federation (Ural Mathematical Center project No. 075-02-2021-1387).
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-85113192800.pdf467,54 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.