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

被引：1

作者：

Huss, Wilfried ^{[1
]}

Sava, Ecaterina ^{[1
]}

Woess, Wolfgang ^{[1
]}

机构：

[1] Graz Univ Technol, Inst Math Strukturtheorie, A-8010 Graz, Austria

来源：

THEORETICAL COMPUTER SCIENCE | 2010年 / 411卷 / 44-46期

基金：

奥地利科学基金会;

关键词：

Formal language; Oriented graph; Infinite sofic system; Growth sensitivity; Entropy; Irreducible Markov chain; Spectral radius; GROWTH; ERGODICITY;

D O I：

10.1016/j.tcs.2010.07.020

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A language L over a finite alphabet Sigma is growth sensitive (or entropy sensitive) if forbidding any finite set of factors F of L yields a sublanguage L-F whose exponential growth rate (entropy) is smaller than that of L. Let (X, E, l) be an infinite, oriented, edge-labelled graph with label alphabet Sigma. Considering the graph as an (infinite) automaton, we associate with any pair of vertices x, y is an element of X the language L-x,L-y consisting of all words that can be read as 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. (C) 2010 Elsevier B.V. All rights reserved.

引用

页码：3917 / 3922

页数：6