Complexity of deep inference via atomic flows

A. Das

Research output: Chapter in Book/Report/Conference proceedingChapter

9 Citations (Scopus)

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.
Original languageEnglish
Title of host publicationHow the World Computes
Subtitle of host publicationTuring Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Cambridge, UK, June 18-23, 2012. Proceedings
EditorsS. Barry Cooper, Anuj Dawar, Benedikt Lowe
Place of PublicationHeidelberg, Germany
PublisherSpringer
Pages139-150
Number of pages12
Volume7318 LNCS
ISBN (Print)9783642308697
DOIs
Publication statusPublished - 2012
EventTuring Centenary Conference and 8th Conference on Computability in Europe, CiE 2012 - Cambridge, UK United Kingdom
Duration: 17 Jun 201222 Jun 2012

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume7318
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceTuring Centenary Conference and 8th Conference on Computability in Europe, CiE 2012
CountryUK United Kingdom
CityCambridge
Period17/06/1222/06/12

Cite this

Das, A. (2012). Complexity of deep inference via atomic flows. In S. B. Cooper, A. Dawar, & B. Lowe (Eds.), How the World Computes: Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Cambridge, UK, June 18-23, 2012. Proceedings (Vol. 7318 LNCS, pp. 139-150). (Lecture Notes in Computer Science; Vol. 7318). Springer. https://doi.org/10.1007/978-3-642-30870-3_15