Complexity of deep inference via atomic flows

Anupam Das

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

Complexity of deep inference via atomic flows

Anupam Das^*

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 language	English
Title of host publication	How the World Computes - Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Proceedings
Pages	139-150
Number of pages	12
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, United Kingdom Duration: 18 Jun 2012 → 23 Jun 2012

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7318 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

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

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

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

Cite this

Das, A. (2012). Complexity of deep inference via atomic flows. In How the World Computes - Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Proceedings (pp. 139-150). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7318 LNCS). https://doi.org/10.1007/978-3-642-30870-3_15

@inproceedings{05f3669548df4109b069165e06caeb6d,

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 = "Anupam Das",

year = "2012",

doi = "10.1007/978-3-642-30870-3_15",

language = "English",

isbn = "9783642308697",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "139--150",

booktitle = "How the World Computes - Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Proceedings",

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

}

Das, A 2012, Complexity of deep inference via atomic flows. in How the World Computes - Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7318 LNCS, pp. 139-150, Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Cambridge, United Kingdom, 18/06/12. https://doi.org/10.1007/978-3-642-30870-3_15

Complexity of deep inference via atomic flows. / Das, Anupam.
How the World Computes - Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Proceedings. 2012. p. 139-150 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7318 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Complexity of deep inference via atomic flows

AU - Das, Anupam

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://www.scopus.com/inward/record.url?scp=84862222493&partnerID=8YFLogxK

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

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

M3 - Conference contribution

AN - SCOPUS:84862222493

SN - 9783642308697

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 139

EP - 150

BT - How the World Computes - Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Proceedings

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

Y2 - 18 June 2012 through 23 June 2012

ER -

Complexity of deep inference via atomic flows

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this