Formal Languages and Automata in Computational Algebra

This thesis is a collection of six papers in computational algebra. In particular, we study noncommutative Gröb- ner bases, SAGBI bases and similar algebraic objects which can be represented as a graph or an automaton. In Paper I we introduce the concept of bi-automaton algebras, generalizing the automaton algebras previously defined by Ufnarovski. A bi-automaton algebra is a quotient of the free algebra, defined by a binomial ideal ad- mitting a Gröbner basis which can be encoded as a regular set; we call such a Gröbner basis regular. We give several examples of bi-automaton algebras, and show how automata associated with regular Gröbner bases can be used to perform reduction. In Paper II the notion of rational Gröbner bases for ideals in the noncommutative polynomial ring is introdu-ced. These are Gröbner bases which can be represented by rational transducers. We study their properties and provide several examples of algebras admitting rational Gröbner bases. Finally, we suggest how to apply the theory to other canonical bases, such as SAGBI bases. In Paper III we introduce an equivalence relation on the class of finite automata, where elements in the same equivalence class accept a common finite sublanguage. This relation will be used to algorithmically recreate a given automaton M, just by considering a sufficiently large finite subset of words accepted by M. Finally, appli-cations of this algorithm to computation of infinite Gröbner bases in the noncommutative polynomial ring are discussed. In Paper IV we investigate various important properties of regular languages associated with quotients of the free associative algebra. We suggest a generalization of a graph for normal words introduced by Ufnarovski, applicable to testing Noetherian properties of automaton algebras. Finally we show an alternative way to comp-ute the generators for the Jacobson radical of any automaton monomial algebra. In Paper V we construct finite automata which accept the languages of normal words and n-chains of any given regular language. We show how these automata can be used to compute the Hilbert series and monomial Poin-caré series of any noncommutative graded algebra which admits a Gröbner basis with a regular language of leading words. In Paper VI we study Gröbner bases for one-sided free A-modules An, where A is a quotient of the noncommu-tative polynomial ring, and we show how these bases can be used to compute minimal free resolutions of finitely generated graded A-modules. Finally, we study a class of free modules An, so called DT-modules, for which all Gröbner bases computations terminate