Complexity of deep inference via atomic flows

A. Das

doi:10.1007/978-3-642-30870-3_15

Complexity of deep inference via atomic flows

A. Das

Department of Computer Science

Research output: Chapter or section in a book/report/conference proceeding › Book chapter

9 Citations (SciVal)

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 language	English
Title of host publication	How the World Computes
Subtitle of host publication	Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Cambridge, UK, June 18-23, 2012. Proceedings
Editors	S. Barry Cooper, Anuj Dawar, Benedikt Lowe
Place of Publication	Heidelberg, Germany
Publisher	Springer
Pages	139-150
Number of pages	12
Volume	7318 LNCS
ISBN (Print)	9783642308697
DOIs	https://doi.org/10.1007/978-3-642-30870-3_15
Publication status	Published - 2012
Event	Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012 - Cambridge, UK United Kingdom Duration: 17 Jun 2012 → 22 Jun 2012

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	7318
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012
Country/Territory	UK United Kingdom
City	Cambridge
Period	17/06/12 → 22/06/12

Access to Document

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

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

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 or section in a book/report/conference proceeding › Book chapter

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). doi: 10.1007/978-3-642-30870-3_15

@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",

note = "Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012 ; Conference date: 17-06-2012 Through 22-06-2012",

}

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

UR - https://www.scopus.com/pages/publications/84862222493

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

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

M3 - Book 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

T2 - Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012

Y2 - 17 June 2012 through 22 June 2012

ER -

Complexity of deep inference via atomic flows

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this