Formal Languages and Automata in Computational Algebra
(2002) 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... (More)
 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. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/464716
 author
 Månsson, Jonas ^{LU}
 opponent

 Professor Green, Edward, Virginia Tech, USA
 organization
 publishing date
 2002
 type
 Thesis
 publication status
 published
 subject
 keywords
 control, Datalogi, Talteori, algebraisk geometri, algebra, gruppteori, Computer science, numerical analysis, systems, group theory, field theory, algebraic geometry, finite automata, Number Theory, Gröbner bases, SAGBI bases, numerisk analys, system, kontroll, fältteori
 pages
 206 pages
 publisher
 Centre for Mathematical Sciences, Lund University
 defense location
 Matematikhuset MH:C
 defense date
 20020617 10:15
 ISSN
 14040034
 ISBN
 9162852930
 language
 English
 LU publication?
 yes
 id
 f4fbb18cf3694d6ebe6c47f26ef2e7be (old id 464716)
 date added to LUP
 20070927 15:56:32
 date last changed
 20170313 14:26:20
@phdthesis{f4fbb18cf3694d6ebe6c47f26ef2e7be, 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.}, author = {Månsson, Jonas}, isbn = {9162852930}, issn = {14040034}, keyword = {control,Datalogi,Talteori,algebraisk geometri,algebra,gruppteori,Computer science,numerical analysis,systems,group theory,field theory,algebraic geometry,finite automata,Number Theory,Gröbner bases,SAGBI bases,numerisk analys,system,kontroll,fältteori}, language = {eng}, pages = {206}, publisher = {Centre for Mathematical Sciences, Lund University}, school = {Lund University}, title = {Formal Languages and Automata in Computational Algebra}, year = {2002}, }