Research

Complexity of deep inference via atomic flows


Reference:

Das, A., 2012. Complexity of deep inference via atomic flows. In: Cooper, S. B., Dawar, A. and Lowe, B., eds. Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, 2012-06-17 - 2012-06-22, Cambridge. Heidelberg, Germany: Springer, pp. 139-150. (Lecture Notes in Computer Science; 7318)

Related documents:

This repository does not currently have the full-text of this item.
You may be able to access a copy if URLs are provided below. (Contact Author)

Abstract

We consider the fragment of deep inference free of compression mechanisms and compare its proof complexity to other systems, utilising 'atomic flows' to examine size of proofs. Results include a simulation of Resolution and dag-like cut-free Gentzen, as well as a separation from bounded-depth Frege.

Details

Item Type Conference or Workshop Items (UNSPECIFIED)
CreatorsDas, A.
EditorsCooper, S. B., Dawar, A. and Lowe, B.
DOI10.1007/978-3-642-30870-3_15
DepartmentsFaculty of Science > Computer Science
StatusPublished
ID Code31114

Export

Actions (login required)

View Item