2010 Issue №10

This is the sixth paper of a series of papers that will give a survey on several topics on formal languages and automata by using semirings, formal power series, matrices andxed point theory. The sixth paper of this series deals with the basic results in the theory of !-algebraic systems over quemirings generalizing the classical context-free grammars generating languages overnite and innite words. The presentation of these results is based on continuous starsemiring-omegasemimodule pairs. We dene !-algebraic systems and characterize their solutions
of order k by behaviors of algebraic nite automata. These solutions are then set in correspondence to !-context-free languages. Then we introduce rational and algebraic transducers, and abstract !-families of power series over quemirings and prove that rational and algebraic power series of nite and innite words constitute such abstract !-families of power series.