Please use this identifier to cite or link to this item:
Title: Συστήματα επανεγγραφής και ομολογία μονοειδών
Other Titles: Term rewriting systems and homology of monoids
Authors: Μαλλάς, Θεοφάνης
Keywords: Συστήματα επανεγγραφής όρων
Ομολογία μονοειδών
Ομολογιακή άλγεβρα
Αλγεβρική θεωρία
Ομολογία αλγεβρικών θεωριών
Keywords (translated): Term rewriting systems
Homology of monoids
Homological algebra
Algebraic theory
Abstract: Στην παρούσα διπλωματική εργασία, αρχικά, μας απασχολεί το πρόβλημα των λέξεων για τα μονοειδή, το οποίο μπορεί να διατυπωθεί ως εξής: ΄Εστω μία παρουσίαση ενός μονοειδούς με γεννήτορες και ισότητες. Υπάρχει αλγόριθμος που χρησιμοποιεί τις ισότητες και μπορεί να υπολογίσει σε πεπερασμένο χρόνο αν δύο τυχαίες λέξεις των γεννητόρων είναι ίσες; Αν η απάντηση είναι θετική τότε λέμε ότι το πρόβλημα των λέξεων είναι αποκρίσιμο. Παραθέτονται οι κανονικές παρουσιάσεις ενός μονοειδούς και επιδεικνύεται ο τρόπος με τον οποίο μία κανονική παρουσίαση με πεπερασμένους γεννήτορες και ισότητες μας εξασφαλίζει τη λύση του προβλήματος. ΄Ομως, υπάρχει πεπερασμένη κανονική παρουσίαση για κάθε μονοειδές που έχει αποκρίσιμο πρόβλημα; Ορίζονται οι ομολογιακές ομάδες του μονοειδούς και αποδεικνύεται ότι υπάρχει μία ομολογιακή συνθήκη που μας εξασφαλίζει ότι ένα μονοειδές δεν έχει πεπερασμένη κανονική παρουσίαση. Με αυτό απαντάται το παραπάνω ερώτημα αρνητικά με ένα αντιπαράδειγμα. Στη συνέχεια παρουσιάζεται μία επέκταση αυτής της ιδέας στις παρουσιάσεις αλγεβρικών θεωριών. Ορίζονται οι ομολογιακές ομάδες μίας αλγεβρικής θεωρίας και, όπως στην περίπτωση των μονοειδών, αυτές εμπεριέχουν πληροφορίες για το τι παρουσιάσεις μπορεί να επιδέχεται αυτή η θεωρία. Τέλος, υποπτευόμαστε μία βαθύτερη σύνδεση των δύο αυτών, παρόμοιων, εγχειρημάτων και παραθέτουμε τον τρόπο με τον οποίο οι αλγεβρικές θεωρίες είναι μονοειδή αντικείμενα μίας κατάλληλης μονοειδούς κατηγορίας.
Abstract (translated): This master thesis, initially, deals with the word problem of monoids. It can be formulated like this: Let a presentation with generators and relations of a monoid. Is there an algorithm that uses these relations and can compute in finite time if two random words of those generators are equal? If the answer is yes, then we say that the word problem is decidable. Canonical presentations are defined and it is demonstrated how a finite canonical presentation has a decidable word problem. But, are there finite canonical presentations for every monoid that has decidable word problem? Homology groups of monoids are defined and it is shown that there is a homological condition that excludes that a canonical presentation of a given monoid exists. Then a counterexample to the above question is shown. Next we have a small discussion on generalizations of this idea to presentations of algebraic theories. Likewise, as in the case of monoids, homology groups of algebraic theories carries information of what kind of presentations exist. Lastly, suspecting there is a deeper connection between these two similar ventures, algebraic theories are shown to be monoid objects of a suitable monoidal category.
Appears in Collections:Τμήμα Μαθηματικών (ΜΔΕ)

Files in This Item:
File Description SizeFormat 
Διπλωματική Φ.Μ..pdf864.82 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.