Proof Complexity: A Tableau Perspective

Postgraduate Thesis uoadl:1838194 257 Read counter

Unit:
Κατεύθυνση Μαθηματική Λογική
Library of the School of Science
Deposit date:
2017-08-30
Year:
2017
Author:
Papamakarios Theodoros
Supervisors info:
Στάθης Ζάχος, Καθηγητής
Σταύρος Κοσμαδάκης, Καθηγητής
Original Title:
Proof Complexity: A Tableau Perspective
Languages:
English
Translated title:
Proof Complexity: A Tableau Perspective
Summary:
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.
Main subject category:
Science
Keywords:
proof complexity, tableaux, width, depth, consistency property
Index:
No
Number of index pages:
0
Contains images:
Yes
Number of references:
38
Number of pages:
59
mplathesis.pdf (573 KB) Open in new window