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. How the World Computes. Vol. 7318 LNCS. Heidelberg, Germany: Springer-Verlag, pp. 139-150. (Lecture Notes in Computer Science; 7318)

Related documents:

Official URL:

http://dx.doi.org/10.1007/978-3-642-30870-3_15

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.

Export

Actions (login required)