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