|
Organizers |
Morphisms and quasinorms over free semigroups
by
Alexandru Cărăuşu
Dept. of Mathematics, Technical University of Iasi, Romania
The object of this paper is to investigate some properties of certain types of morphisms and operators defined on a free semigroup \Sigma+(or free monoid \Sigma * =\Sigma+ \cup {\lambda}), in connection with some measures associated to parts thereof, that is to formal languages.
If \Sigma and \Delta are two
alphabets, a mapping f:\Sigma * --> \Delta * is a
homomorphism of free monoids if ( for all u, v in \Sigma * ) f(uv)=f(u) f(v). Any homomorphism maps a language L subset or equal \Sigma * on f(L) subset or equal \Delta * . An operator on the set of
languages over the same alphabet \Sigma will be denoted by F. Some
operators can be realized in terms of automata, transducers etc.
A family \QTRcalL of formal
languages may be endowed with a structure of vector space under the linear
operations of ''addition'' (in fact, the disjoint union) L1\dotplusL2\triangleq (L1 \cup L2)\(L1 \cap L2) and
''multiplication by scalars'' in the {0, 1} field, 0L\triangleq\emptyset & 1L\triangleq L. If u=ai1ai2...aim is a
word in L subset \Sigma * , its length is l(u)\triangleq m.
A way to define a norm of a language was proposed as || L ||\triangleq 2-\nu(L) where \nu(L)=min {l(u):u in L}. There
are grounds for considering other types of norms or quasinorms, able to
take into account the way L is generated / accepted by a formal device.
We propose a couple of norms / quasinorms for languages generated by a
formal grammar G=(N, \Sigma, S, P) which take into account the structure of
the words in L and their derivational complexity (using the notion of
index). The definitions are too technical for being given in this abstract.
The norms thus defined allow to classify operators on families of
languages, e.g. to introduce bounded and contractive operators.
Date received: April 5, 2000
Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caex-58.