Μονάδα:
Διαπανεπιστημιακό ΠΜΣ Λογική και Θεωρία Αλγορίθμων και ΥπολογισμούΒιβλιοθήκη Σχολής Θετικών Επιστημών
Ημερομηνία κατάθεσης:
2014-01-24
Συγγραφέας:
Ξουράφης Γεώργιος
Στοιχεία επιβλεπόντων καθηγητών:
Γεώργιος Κολέτσος Καθηγητής ΕΜΠ (επιβλέπων)Κωνσταντίνος Δημητρακόπουλος Καθηγητής ΕΚΠΑ, Νικόλαος Ρήγας Διδάκτωρ
Πρωτότυπος Τίτλος:
Ατέρμονες αναγωγές στον λ-λογισμό
Γλώσσες εργασίας:
Ελληνικά
Μεταφρασμένος τίτλος:
Perpetual reductions in λ-calculus
Περίληψη:
Οι ατέρμονες στρατηγικές είναι ένα εργαλείο που βοήθησε στην απόδειξη και
κατανόηση κάποιων ιδιοτήτων της β-αναγωγής (και όχι μόνο). Μια σημαντική
εφαρμογή αυτού του εργαλείου αφορά την απόδειξη του θεωρήματος του Sorensen,
ενώ μια άλλη σχετίζεται με τον χαρακτηρισμό των ατερμόνων redexes ενός λ-όρου,
δηλαδή ποια redexes πρέπει να συστείλουμε ώστε να διαιωνίσουμε μια β-αναγωγή.
Ένας εναλλακτικός τρόπος εξαγωγής αυτών των συμπερασμάτων είναι η μέθοδος της
τυποποίησης, την οποία μελετάμε στο τελευταίο κεφάλαιο αυτής της εργασίας.
Λέξεις-κλειδιά:
β-αναγωγές, Στρατηγικές, Ατέρμονες, Τυποποίηση, Θεώρημα Sorensen
Αρ. σελίδων ευρετηρίου:
0
Αρ. βιβλιογραφικών αναφορών:
4
Αριθμός σελίδων:
[14], 81
