Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
M. Müller, St. Szeider:
"Revisiting Space in Proof Complexity: Treewidth and Pathwidth";
Vortrag: International Symposium on Mathematical Foundations of Computer Science (MFCS),
Klosterneuburg, Austria;
26.08.2013
- 30.08.2013; in: "The 38th International Symposium on Mathematical Foundations of Computer Science, Proceedings",
K. Chatterjee, J. Sgall (Hrg.);
Springer / LNCS,
8087
(2013),
ISBN: 978-3-642-40312-5;
S. 704
- 716.
Kurzfassung englisch:
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.
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-642-40313-2_41
Zugeordnete Projekte:
Projektleitung Stefan Szeider:
The Parameterized Complexity of Reasoning Problems
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.