δείτε την πρωτότυπη σελίδα τεκμηρίου στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
Η μέθοδος των σημασιολογικών tableaux (ή απλά tableaux) είναι αναμφίβολα ένα από τα πιο κομψά αποδεικτικά συστήματα.
Δυστυχώς, δεν έχει λάβει την απαραίτητη προσοχή στην βιβλιογραφία της πολυπλοκότητας αποδείξεων, κυρίως λόγω αρνητικών αποτελεσμάτων που αφορούν την πολυπλοκότητα των χωρίς-τομών tableau αποδείξεων. Φέρνουμε τα tableaux στο προσκήνιο, εισάγοντας τις μετρικές των tableau βάθους και πλάτους. Έχοντας αυτές, δείχνουμε
με έναν ομοιόμορφο, κομψό τρόπο γνωστά αποτελέσματα που καλύπτουν την πολυπλοκότητα αποδείξεων, από μια tableau οπτική.
(EL)
The method of semantic tableaux (or simply tableaux) is arguably
one of the most elegant proof systems. Unfortunately, it hasn’t received
much attention in the proof complexity literature, mainly due to early
negative results, concerning the complexity of cut-free tableaux. We bring tableaux to the fore, introducing the
measures of tableau depth and width. Equipped with these, we show in
an elegant, uniform way several known results spanning proof complexity,
from a tableau viewpoint.
(EN)
*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.
Βοηθείστε μας να κάνουμε καλύτερο το OpenArchives.gr.
Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
