Record link: 
http://hdl.handle.net/20.500.12708/54880
-
Title: 
Revisiting Space in Proof Complexity: Treewidth and Pathwidth
-
Citation: 
Müller, M., & Szeider, S. (2013). Revisiting Space in Proof Complexity: Treewidth and Pathwidth. In K. Chatterjee & J. Sgall (Eds.), Mathematical Foundations of Computer Science 2013 (pp. 704–716). Springer / LNCS. https://doi.org/10.1007/978-3-642-40313-2_62
-
Publisher DOI: 
10.1007/978-3-642-40313-2_62
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Authors: 
Müller, Moritz 
Szeider, Stefan 
-
Organisational Unit: 
E192-03 - Forschungsbereich Knowledge Based Systems 
-
Published in: 
Mathematical Foundations of Computer Science 2013 
-
ISBN: 
978-3-642-40312-5
-
Volume: 
8087
-
DOI of the book: 
10.1007/978-3-642-40313-2
-
Date (published): 
2013
-
Event name: 
International Symposium on Mathematical Foundations of Computer Science (MFCS) 
-
Event date: 
26-Aug-2013 - 30-Aug-2013
-
Event place: 
Klosterneuburg, Austria, Austria
-
Number of Pages: 
13
-
Publisher: 
Springer / LNCS, 8087
-
Publisher: 
Springer Berlin, Heidelberg
-
Peer reviewed: 
Yes
-
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
Project title: 
The Parameterized Complexity of Reasoning Problems: 239962 (Europäischer Forschungsrat (ERC)) 
-
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
Mathematik, Informatik
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

196
checked on Nov 22, 2023

Google ScholarTM

Check