Journal
THEORETICAL COMPUTER SCIENCE
Volume 307, Issue 1, Pages 93-102Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/S0304-3975(03)00094-X
Keywords
regular language; entropy; oriented graph; free group; hopfianity
Categories
Ask authors/readers for more resources
Let L be an irreducible regular language. Let W be a non-empty set of words (or sub-words) of L and denote by L-W = {v is an element of L:w not subset of v, For Allw is an element of W} the language obtained from L by forbidding all the words w in W. Then the entropy decreases strictly: ent(L-W) < ent(L). In this note we present a new proof of this fact, based on a method of Gromov, which avoids the Perron-Frobenius theory. This result applies to the regular languages of finitely generated free groups and an additional application is presented. (C) 2003 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available