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.
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11573/251267
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 9
social impact