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.
On the entropy of regular languages / Scarabotti, Fabio; Machi', Antonio; Tullio Ceccherini, Silberstein. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 307:1 SPEC.(2003), pp. 93-102. (Intervento presentato al convegno 3rd Conference on WORDS tenutosi a PALERMO, ITALY nel SEP, 2001) [10.1016/s0304-3975(03)00094-x].
On the entropy of regular languages
SCARABOTTI, Fabio;MACHI', Antonio;
2003
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
