Συστήματα επανεγγραφής και ομολογία μονοειδών
Στην παρούσα διπλωματική εργασία, αρχικά, μας απασχολεί το πρόβλημα των λέξεων για τα μονοειδή, το οποίο μπορεί να διατυπωθεί ως εξής: ΄Εστω μία παρουσίαση ενός μονοειδούς με γεννήτορες και ισότητες. Υπάρχει αλγόριθμος που χρησιμοποιεί τις ισότητες και μπορεί να υπολογίσει σε πεπερασμένο χρόνο αν δύ...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Μορφή: | Thesis |
| Γλώσσα: | Greek |
| Έκδοση: |
2019
|
| Θέματα: | |
| Διαθέσιμο Online: | http://hdl.handle.net/10889/12878 |
| id |
nemertes-10889-12878 |
|---|---|
| record_format |
dspace |
| spelling |
nemertes-10889-128782022-09-05T20:27:39Z Συστήματα επανεγγραφής και ομολογία μονοειδών Term rewriting systems and homology of monoids Μαλλάς, Θεοφάνης Καραζέρης, Παναγής Τζερμιάς, Παύλος Λεντούδης, Παύλος Mallas, Theofanis Συστήματα επανεγγραφής όρων Ομολογία μονοειδών Ομολογιακή άλγεβρα Αλγεβρική θεωρία Ομολογία αλγεβρικών θεωριών Term rewriting systems Homology of monoids Homological algebra Algebraic theory Στην παρούσα διπλωματική εργασία, αρχικά, μας απασχολεί το πρόβλημα των λέξεων για τα μονοειδή, το οποίο μπορεί να διατυπωθεί ως εξής: ΄Εστω μία παρουσίαση ενός μονοειδούς με γεννήτορες και ισότητες. Υπάρχει αλγόριθμος που χρησιμοποιεί τις ισότητες και μπορεί να υπολογίσει σε πεπερασμένο χρόνο αν δύο τυχαίες λέξεις των γεννητόρων είναι ίσες; Αν η απάντηση είναι θετική τότε λέμε ότι το πρόβλημα των λέξεων είναι αποκρίσιμο. Παραθέτονται οι κανονικές παρουσιάσεις ενός μονοειδούς και επιδεικνύεται ο τρόπος με τον οποίο μία κανονική παρουσίαση με πεπερασμένους γεννήτορες και ισότητες μας εξασφαλίζει τη λύση του προβλήματος. ΄Ομως, υπάρχει πεπερασμένη κανονική παρουσίαση για κάθε μονοειδές που έχει αποκρίσιμο πρόβλημα; Ορίζονται οι ομολογιακές ομάδες του μονοειδούς και αποδεικνύεται ότι υπάρχει μία ομολογιακή συνθήκη που μας εξασφαλίζει ότι ένα μονοειδές δεν έχει πεπερασμένη κανονική παρουσίαση. Με αυτό απαντάται το παραπάνω ερώτημα αρνητικά με ένα αντιπαράδειγμα. Στη συνέχεια παρουσιάζεται μία επέκταση αυτής της ιδέας στις παρουσιάσεις αλγεβρικών θεωριών. Ορίζονται οι ομολογιακές ομάδες μίας αλγεβρικής θεωρίας και, όπως στην περίπτωση των μονοειδών, αυτές εμπεριέχουν πληροφορίες για το τι παρουσιάσεις μπορεί να επιδέχεται αυτή η θεωρία. Τέλος, υποπτευόμαστε μία βαθύτερη σύνδεση των δύο αυτών, παρόμοιων, εγχειρημάτων και παραθέτουμε τον τρόπο με τον οποίο οι αλγεβρικές θεωρίες είναι μονοειδή αντικείμενα μίας κατάλληλης μονοειδούς κατηγορίας. 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. 2019-12-21T08:57:01Z 2019-12-21T08:57:01Z 2019-07-30 Thesis http://hdl.handle.net/10889/12878 gr 0 application/pdf |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Συστήματα επανεγγραφής όρων Ομολογία μονοειδών Ομολογιακή άλγεβρα Αλγεβρική θεωρία Ομολογία αλγεβρικών θεωριών Term rewriting systems Homology of monoids Homological algebra Algebraic theory |
| spellingShingle |
Συστήματα επανεγγραφής όρων Ομολογία μονοειδών Ομολογιακή άλγεβρα Αλγεβρική θεωρία Ομολογία αλγεβρικών θεωριών Term rewriting systems Homology of monoids Homological algebra Algebraic theory Μαλλάς, Θεοφάνης Συστήματα επανεγγραφής και ομολογία μονοειδών |
| description |
Στην παρούσα διπλωματική εργασία, αρχικά, μας απασχολεί το πρόβλημα των λέξεων για τα μονοειδή, το οποίο μπορεί να διατυπωθεί ως εξής: ΄Εστω μία παρουσίαση ενός μονοειδούς με γεννήτορες και ισότητες. Υπάρχει αλγόριθμος που χρησιμοποιεί τις ισότητες και μπορεί να υπολογίσει σε πεπερασμένο χρόνο αν δύο τυχαίες λέξεις των γεννητόρων είναι ίσες; Αν η απάντηση είναι θετική τότε λέμε ότι το πρόβλημα των λέξεων είναι αποκρίσιμο. Παραθέτονται οι κανονικές παρουσιάσεις ενός μονοειδούς και επιδεικνύεται ο τρόπος με τον οποίο μία κανονική παρουσίαση με πεπερασμένους γεννήτορες και ισότητες μας εξασφαλίζει τη λύση του προβλήματος. ΄Ομως, υπάρχει πεπερασμένη κανονική παρουσίαση για κάθε μονοειδές που έχει αποκρίσιμο πρόβλημα; Ορίζονται οι ομολογιακές ομάδες του μονοειδούς και αποδεικνύεται ότι υπάρχει μία ομολογιακή συνθήκη που μας εξασφαλίζει ότι ένα μονοειδές δεν έχει πεπερασμένη κανονική παρουσίαση. Με αυτό απαντάται το παραπάνω ερώτημα αρνητικά με ένα αντιπαράδειγμα. Στη συνέχεια παρουσιάζεται μία επέκταση αυτής της ιδέας στις παρουσιάσεις αλγεβρικών θεωριών. Ορίζονται οι ομολογιακές ομάδες μίας αλγεβρικής θεωρίας και, όπως στην περίπτωση των μονοειδών, αυτές εμπεριέχουν πληροφορίες για το τι παρουσιάσεις μπορεί να επιδέχεται αυτή η θεωρία. Τέλος, υποπτευόμαστε μία βαθύτερη σύνδεση των δύο αυτών, παρόμοιων, εγχειρημάτων και παραθέτουμε τον τρόπο με τον οποίο οι αλγεβρικές θεωρίες είναι μονοειδή αντικείμενα μίας κατάλληλης μονοειδούς κατηγορίας. |
| author2 |
Καραζέρης, Παναγής |
| author_facet |
Καραζέρης, Παναγής Μαλλάς, Θεοφάνης |
| format |
Thesis |
| author |
Μαλλάς, Θεοφάνης |
| author_sort |
Μαλλάς, Θεοφάνης |
| title |
Συστήματα επανεγγραφής και ομολογία μονοειδών |
| title_short |
Συστήματα επανεγγραφής και ομολογία μονοειδών |
| title_full |
Συστήματα επανεγγραφής και ομολογία μονοειδών |
| title_fullStr |
Συστήματα επανεγγραφής και ομολογία μονοειδών |
| title_full_unstemmed |
Συστήματα επανεγγραφής και ομολογία μονοειδών |
| title_sort |
συστήματα επανεγγραφής και ομολογία μονοειδών |
| publishDate |
2019 |
| url |
http://hdl.handle.net/10889/12878 |
| work_keys_str_mv |
AT mallastheophanēs systēmataepanengraphēskaiomologiamonoeidōn AT mallastheophanēs termrewritingsystemsandhomologyofmonoids |
| _version_ |
1771297279581356032 |
