<div class="csl-bib-body">
<div class="csl-entry">Müller, M., & Szeider, S. (2013). Revisiting Space in Proof Complexity: Treewidth and Pathwidth. In K. Chatterjee & J. Sgall (Eds.), <i>Mathematical Foundations of Computer Science 2013</i> (pp. 704–716). Springer / LNCS. https://doi.org/10.1007/978-3-642-40313-2_62</div>
</div>
-
dc.identifier.isbn
9783642403125
-
dc.identifier.isbn
9783642403132
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/54880
-
dc.description.abstract
So-called ordered variants of the classical notions of pathwidth and treewidth are introduced and proposed as proof theoretically meaningful complexity measures for the directed acyclic graphs underlying proofs. The ordered pathwidth of a proof is shown to be roughly the same as its formula space. Length-space lower bounds for R(k)-refutations are generalized to arbitrary infinity axioms and strengthened in that the space measure is relaxed to ordered treewidth.
en
dc.description.sponsorship
Europäischer Forschungsrat (ERC)
-
dc.publisher
Springer / LNCS
-
dc.relation.ispartofseries
Lecture Notes in Computer Science
-
dc.title
Revisiting Space in Proof Complexity: Treewidth and Pathwidth
-
dc.type
Konferenzbeitrag
de
dc.type
Inproceedings
en
dc.relation.publication
Mathematical Foundations of Computer Science 2013
-
dc.relation.isbn
978-3-642-40312-5
-
dc.relation.doi
10.1007/978-3-642-40313-2
-
dc.relation.issn
0302-9743
-
dc.description.startpage
704
-
dc.description.endpage
716
-
dc.relation.grantno
239962
-
dc.type.category
Full-Paper Contribution
-
dc.relation.eissn
1611-3349
-
dc.publisher.place
8087
-
tuw.booktitle
Mathematical Foundations of Computer Science 2013
-
tuw.container.volume
8087
-
tuw.peerreviewed
true
-
tuw.relation.publisher
Springer Berlin, Heidelberg
-
tuw.book.chapter
62
-
tuw.project.title
The Parameterized Complexity of Reasoning Problems
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192-03 - Forschungsbereich Knowledge Based Systems
-
tuw.publisher.doi
10.1007/978-3-642-40313-2_62
-
dc.description.numberOfPages
13
-
tuw.event.name
International Symposium on Mathematical Foundations of Computer Science (MFCS)
-
tuw.event.startdate
26-08-2013
-
tuw.event.enddate
30-08-2013
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Klosterneuburg, Austria
-
tuw.event.place
Klosterneuburg, Austria
-
tuw.event.country
AT
-
tuw.event.presenter
Müller, Moritz
-
wb.sciencebranch
Mathematik, Informatik
-
wb.sciencebranch.oefos
11
-
wb.presentation.type
science to science/art to art
-
item.openairetype
conference paper
-
item.grantfulltext
none
-
item.fulltext
no Fulltext
-
item.cerifentitytype
Publications
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
