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). Heidelberg, Germany: Springer. https://doi.org/10.1007/978-3-642-30870-3_15

Complexity of deep inference via atomic flows. / Das, A.

How the World Computes: Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Cambridge, UK, June 18-23, 2012. Proceedings. ed. / S. Barry Cooper; Anuj Dawar; Benedikt Lowe. Vol. 7318 LNCS Heidelberg, Germany : Springer, 2012. p. 139-150 (Lecture Notes in Computer Science; Vol. 7318).

Research output: Chapter in Book/Report/Conference proceedingChapter

Das, A 2012, Complexity of deep inference via atomic flows. in SB 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, Lecture Notes in Computer Science, vol. 7318, Springer, Heidelberg, Germany, pp. 139-150, Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Cambridge, UK United Kingdom, 17/06/12. https://doi.org/10.1007/978-3-642-30870-3_15
Das A. Complexity of deep inference via atomic flows. In Cooper SB, Dawar A, Lowe B, editors, 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. Heidelberg, Germany: Springer. 2012. p. 139-150. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-30870-3_15
Das, A. / Complexity of deep inference via atomic flows. How the World Computes: Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Cambridge, UK, June 18-23, 2012. Proceedings. editor / S. Barry Cooper ; Anuj Dawar ; Benedikt Lowe. Vol. 7318 LNCS Heidelberg, Germany : Springer, 2012. pp. 139-150 (Lecture Notes in Computer Science).
@inbook{a0d9607711e24ae383db3cf7df1246d0,
title = "Complexity of deep inference via atomic flows",
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.",
author = "A. Das",
year = "2012",
doi = "10.1007/978-3-642-30870-3_15",
language = "English",
isbn = "9783642308697",
volume = "7318 LNCS",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "139--150",
editor = "Cooper, {S. Barry} and Anuj Dawar and Benedikt Lowe",
booktitle = "How the World Computes",

}

TY - CHAP

T1 - Complexity of deep inference via atomic flows

AU - Das, A.

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

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

U2 - 10.1007/978-3-642-30870-3_15

DO - 10.1007/978-3-642-30870-3_15

M3 - Chapter

SN - 9783642308697

VL - 7318 LNCS

T3 - Lecture Notes in Computer Science

SP - 139

EP - 150

BT - How the World Computes

A2 - Cooper, S. Barry

A2 - Dawar, Anuj

A2 - Lowe, Benedikt

PB - Springer

CY - Heidelberg, Germany

ER -