Entropy sensitivity of languages defined by infinite automata, via Markov chains with forbidden transitions Export

@article{citeulike:6060450, abstract = {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.}, archivePrefix = {arXiv}, author = {Huss, Wilfried and Sava, Ecaterina and Woess, Wolfgang}, citeulike-article-id = {6060450}, citeulike-linkout-0 = {http://arxiv.org/abs/0911.0142}, citeulike-linkout-1 = {http://arxiv.org/pdf/0911.0142}, day = {1}, eprint = {0911.0142}, keywords = {automaton, entropy, hmm, language}, month = {Nov}, posted-at = {2009-11-03 15:13:29}, priority = {2}, title = {Entropy sensitivity of languages defined by infinite automata, via Markov chains with forbidden transitions}, url = {http://arxiv.org/abs/0911.0142}, year = {2009} }

TY - JOUR ID - citeulike:6060450 L3 - citeulike-article-id:6060450 N2 - 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. TI - Entropy sensitivity of languages defined by infinite automata, via Markov chains with forbidden transitions KW - automaton KW - entropy KW - hmm KW - language AU - Huss, Wilfried AU - Sava, Ecaterina AU - Woess, Wolfgang PY - 2009/Nov/01/ UR - http://arxiv.org/abs/0911.0142 ER -