Proof Complexity: A Tableau Perspective

Διπλωματική Εργασία uoadl:1838194 241 Αναγνώσεις

Μονάδα:
Κατεύθυνση Μαθηματική Λογική
Βιβλιοθήκη Σχολής Θετικών Επιστημών
Ημερομηνία κατάθεσης:
2017-08-30
Έτος εκπόνησης:
2017
Συγγραφέας:
Παπαμακάριος Θεόδωρος
Στοιχεία επιβλεπόντων καθηγητών:
Στάθης Ζάχος, Καθηγητής
Σταύρος Κοσμαδάκης, Καθηγητής
Πρωτότυπος Τίτλος:
Proof Complexity: A Tableau Perspective
Γλώσσες εργασίας:
Αγγλικά
Μεταφρασμένος τίτλος:
Πολυπλοκότητα Αποδείξεων: Μια Tableau Οπτική
Περίληψη:
Η μέθοδος των σημασιολογικών tableaux (ή απλά tableaux) είναι αναμφίβολα ένα από τα πιο κομψά αποδεικτικά συστήματα.
Δυστυχώς, δεν έχει λάβει την απαραίτητη προσοχή στην βιβλιογραφία της πολυπλοκότητας αποδείξεων, κυρίως λόγω αρνητικών αποτελεσμάτων που αφορούν την πολυπλοκότητα των χωρίς-τομών tableau αποδείξεων. Φέρνουμε τα tableaux στο προσκήνιο, εισάγοντας τις μετρικές των tableau βάθους και πλάτους. Έχοντας αυτές, δείχνουμε
με έναν ομοιόμορφο, κομψό τρόπο γνωστά αποτελέσματα που καλύπτουν την πολυπλοκότητα αποδείξεων, από μια tableau οπτική.
Κύρια θεματική κατηγορία:
Θετικές Επιστήμες
Λέξεις-κλειδιά:
πολυπλοκότητα αποδείξεων, tableaux, πλάτος, βάθος, ιδιότητα συνέπειας
Ευρετήριο:
Όχι
Αρ. σελίδων ευρετηρίου:
0
Εικονογραφημένη:
Ναι
Αρ. βιβλιογραφικών αναφορών:
38
Αριθμός σελίδων:
59