Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
http://dx.doi.org/10.18419/opus-14346
Autor(en): | Natterer, Silas |
Titel: | Quadratic equations in free groups and free monoids |
Erscheinungsdatum: | 2024 |
Dokumentart: | Abschlussarbeit (Bachelor) |
Seiten: | 17 |
URI: | http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-ds-143659 http://elib.uni-stuttgart.de/handle/11682/14365 http://dx.doi.org/10.18419/opus-14346 |
Zusammenfassung: | 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. |
Enthalten in den Sammlungen: | 05 Fakultät Informatik, Elektrotechnik und Informationstechnik |
Dateien zu dieser Ressource:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
Bachelorarbeit_SilasNatterer.pdf | 383,89 kB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repositorium sind urheberrechtlich geschützt.