Bounded weight functions on regular languages and groups

Abstract

We introduce the notion of a bounded weight function on a language and show that the set of bounded weight functions on a regular language is a rational polyhedral cone. We study the cell recognised by a bounded weight function (i.e., the set of elements of the language where the bound is attained) and show that if the language is regular, then this cell is regular. The related notion of a weight function on a finitely generated group is introduced, and the case of Coxeter groups is studied in detail. Applications to the representation theory of weighted Hecke algebras are given.