Advanced

Formal Languages and Automata in Computational Algebra

Månsson, Jonas LU (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 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... (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 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. (Less)
Please use this url to cite or link to this publication:
author
opponent
  • Professor Green, Edward, Virginia Tech, USA
organization
publishing date
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
2002-06-17 10:15
ISSN
1404-0034
ISBN
91-628-5293-0
language
English
LU publication?
yes
id
f4fbb18c-f369-4d6e-be6c-47f26ef2e7be (old id 464716)
date added to LUP
2007-09-27 15:56:32
date last changed
2017-03-13 14:26:20
@phdthesis{f4fbb18c-f369-4d6e-be6c-47f26ef2e7be,
  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 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.},
  author       = {Månsson, Jonas},
  isbn         = {91-628-5293-0},
  issn         = {1404-0034},
  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},
}