1. Home page
  2. Search

Proof Complexity: A Tableau Perspective

This item is provided by the institution :
/aggregator-openarchives/portal/institutions/uoa   

Repository :
Pergamos Digital Library   

see the original item page
in the repository's web site and access all digital files if the item*



Proof Complexity: A Tableau Perspective
Παπαμακάριος Θεόδωρος (EL)
Papamakarios Theodoros (EN)
born_digital_postgraduate_thesis
Διπλωματική Εργασία (EL)
Postgraduate Thesis (EN)
2017
Η μέθοδος των σημασιολογικών 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)
Θετικές Επιστήμες
Θετικές Επιστήμες (EL)
Science (EN)
English
Σχολή Θετικών Επιστημών » Τμήμα Μαθηματικών » Διαπανεπιστημιακό ΠΜΣ Λογική και Θεωρία Αλγορίθμων και Υπολογισμού » Κατεύθυνση Μαθηματική Λογική
Βιβλιοθήκη και Κέντρο Πληροφόρησης » Βιβλιοθήκη Σχολής Θετικών Επιστημών
https://creativecommons.org/licenses/by-nc/4.0/
University of Athens
Pergamos Digital Library
Postgraduate Thesis



*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)