Formal Languages and Automata in Computational Algebra

Research output: ThesisDoctoral 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 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.

Details

Authors
Organisations
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Mathematics

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
Original languageEnglish
QualificationDoctor
Awarding Institution
Supervisors/Assistant supervisor
  • [unknown], [unknown], Supervisor, External person
Award date2002 Jun 17
Publisher
  • Centre for Mathematical Sciences, Lund University
Print ISBNs91-628-5293-0
Publication statusPublished - 2002
Publication categoryResearch

Bibliographic note

Defence details Date: 2002-06-17 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