Bachelor Thesis BCLR-2024-18

BibliographyNatterer, Silas: Quadratic equations in free groups and free monoids.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Bachelor Thesis No. 18 (2024).
17 pages, english.
Abstract

We consider word equations over a free monoid or group where every variable occurs at most twice, also called quadratic equations. First, we recount some previously established facts about quadratic equations. We then present the classic solution algorithm for quadratic equations over free monoids based on Nielsen transformations. Next, we prove a theorem that is in some ways analogous to the Pumping Lemma for regular languages: If a quadratic equation permits infinitely many solutions, this already implies the existence of solutions with arbitrarily high exponent of periodicity; this statement is proven both for free monoids and free groups. Finally, we present an algorithm which computes the exponent of periodicity for general equations over free monoids.

Full text and
other links
Volltext
Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
Superviser(s)Diekert, Prof. Volker
Entry dateOctober 16, 2024
New Report   New Article   New Monograph   Department   Institute   Computer Science