Formal Languages and Automata in Computational Algebra
Research output: Thesis › Doctoral Thesis (compilation)
Abstract
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 biautomaton algebras, generalizing the automaton algebras previously defined by Ufnarovski. A biautomaton 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 biautomaton 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 introduced. 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, applications 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 compute 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 nchains of any given regular language. We show how these automata can be used to compute the Hilbert series and monomial Poincaré 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 onesided free Amodules An, where A is a quotient of the noncommutative polynomial ring, and we show how these bases can be used to compute minimal free resolutions of finitely generated graded Amodules. Finally, we study a class of free modules An, so called DTmodules, for which all Gröbner bases computations terminate.
Details
Authors  

Organisations  
Research areas and keywords  Subject classification (UKÄ) – MANDATORY
Keywords

Original language  English 

Qualification  Doctor 
Awarding Institution  
Supervisors/Assistant supervisor 

Award date  2002 Jun 17 
Publisher 

Print ISBNs  9162852930 
Publication status  Published  2002 
Publication category  Research 
Bibliographic note
Defence details
Date: 20020617
Time: 10:15
Place: Matematikhuset MH:C
External reviewer(s)
Name: Green, Edward
Title: Professor
Affiliation: Virginia Tech, USA

Paper I J. Månsson, P.Nordbeck: Regular Gröbner bases
Paper II J. Månsson: Rational Gröbner bases
Paper III J. Månsson: A prediction algorithm for regular languages
Paper IV J. Månsson, P. Nordbeck: Use of graphs for automaton algebras
Paper V J. Månsson: On the computation of Hilbert series and Poincaré series for algebras with infinite Gröbner bases
Paper VI J. Månsson: On the computation of minimal free resolutions