





















A language L over a finite alphabet is growth-sensitive (or entropy sensitive) if forbidding any set of subwords F yields a sub-language L^F whose exponential growth rate (entropy) is smaller than that of L. Let (X, E, l) be an infinite, oriented, labelled graph. Considering the graph as an (infinite) automaton, we associate with any pair of vertices x,y in X the language consisting of all words that can be read as the labels along some path from x to y. Under suitable, general assumptions we prove that these languages are growth-sensitive. This is based on using Markov chains with forbidden transitions.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。