Lyndon λέξεις και Shuffle άλγεβρα:
Creators: name: Αβραμίδου, Μαρία Ιωάννη
Publisher: name: Aristotle University of Thessaloniki
Year: 2012
Subjects: Αλγεβρα
Σαφλ Γινόμενο
Λίντον Λέξεις
Algebra
Shuffle product
Lyndon Words

description: Στην παρούσα διπλωματική εργασία θα μελετήσουμε την Shuffle άλγεβρα με την βοήθεια των Lyndon λέξεων. Οι Lyndon λέξεις πήραν το όνομα τους από τον μαθηματικό Roger Lyndon, ο οποίος τις παρουσίασε το 1954. Λίγα χρόνια αργότερα το 1958 ο Ree εισήγαγε το Shuffle γινόμενο για την μελέτη των Lie πολυωνύμων. Στο πρώτο κεφάλαιο παρουσιάζουμε κάποιες εισαγωγικές έννοιες από την άλγεβρα. Δίνεται ο ορισμός της Lie άλγεβρας και της προσεταιριστικής Κ-άλγεβρας. Η σχέση που υπάρχει μεταξύ αυτών των δύο αλγεβρών περιγράφεται από το θεώρημα των Poincare-Birkorff-Witt. Δίνεται η έννοια των τυπικών σειρών (formal series). Έπειτα ορίζεται το Shuffle γινόμενο, του οποίου θα δούμε τις ιδιότητες και θα δώσουμε μερικά παραδείγματα. Στην συνέχεια δίνουμε τον ορισμό των Lyndon λέξεων, τις ιδιότητες τους και τον ορισμό της κανονικής παραγοντοποίησης μαζί με παραδείγματα που θα βοηθήσουν στην κατανόηση τους. Πριν περάσουμε στις Ελεύθερες Lie Άλγεβρες παραθέτουμε τα θεωρήματα που εξηγούν πως αν w είναι Lyndon λέξη με κανονική παραγοντοποίηση uv τότε u,v είναι Lyndon λέξεις, με u
description: In this thesis, we will study Shuffle algebra with the aid of Lyndon words. Lyndon words were named after the mathematician Roger Lyndon, who presented those in 1954. Some years later, in 1958, Ree introduced Shuffle product to enhance the study of Lie polynomials. In the first chapter we will provide some introductory algebra meanings, plus the definitions of Lie algebra and the associative K-Algebra. The relation between these two algebras is described from Poincare-Birkoff-Witt theorem. The concept of formal series will be presented. The definition of Shuffle product will follow, with its respective properties and some word examples. Thereafter the definitions of Lyndon words and standard factorization will be provided, followed by examples and some properties. Prior to moving on free Lie algebras, two theorems coupled with their proofs will be presented. Algorithms have been constructed, to produce Lyndon words of specific length and finding its standard factorization. Then we will consider some applications using Lyndon polynomials, Hall words and trees. Towards the end of the chapter another two theorems will be proven, in order to demonstrate the direct relations with Lyndon words. These are: the set of Lyndon words, ordered alphabetically, is a Hall set and that the Lyndon polynomials form a basis of free Lie algebra. In chapter 2 we will present the propositions and theorems that are necessary for the proof of the main theorems that are presented in chapter three. In chapter 3 it’s proven that Shuffle algebra Q〈Α〉 is a free commutative algebra over the sum Sl and that Shuffle algebra Q〈Α〉 is freely generated by the Lyndon words. Those two results were the purpose of this thesis. Lyndon words are used in the study of periodic music sequences, who amongst others appear in two particular examples from traditional African music. Berstel and Boasson theorem which proves that Lyndon words sum is not context free, gives a glimpse of how Lyndon words find appliance in theoretical computer science. Furthermore, it’s proven that Shuffle algebra is isoform with the Multilogarithm Algebra. Finally we shall mention that Lyndon’s initial motive for creating and introducing Lyndon words, was the description of a basis forming free Lie Algebra.