Complexity of deep inference via atomic flows


Das, A., 2012. Complexity of deep inference via atomic flows. In: Cooper, S. B., Dawar, A. and Lowe, B., eds. How the World Computes.Vol. 7318 LNCS. 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.

Official URL:


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.


Item Type Book Sections
CreatorsDas, A.
EditorsCooper, S. B., Dawar, A. and Lowe, B.
DepartmentsFaculty of Science > Computer Science
ID Code31114


Actions (login required)

View Item