Bibliograph. Daten | Natterer, Silas: Quadratic equations in free groups and free monoids. Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Bachelorarbeit Nr. 18 (2024). 17 Seiten, englisch.
|
| Kurzfassung | 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.
|
Volltext und andere Links | Volltext
|
| Abteilung(en) | Universität Stuttgart, Institut für Formale Methoden der Informatik, Theoretische Informatik
|
| Betreuer | Diekert, Prof. Volker |
| Eingabedatum | 16. Oktober 2024 |
|---|