Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDSearch dblp for Publications
export results for "narrow proof"
download as .bib file
@article{DBLP:journals/tocl/BeyersdorffCMS18,
author = {Olaf Beyersdorff and
Leroy Chew and
Meena Mahajan and
Anil Shukla},
title = {Are Short Proofs Narrow? {QBF} Resolution Is \emph{Not} So Simple},
journal = {{ACM} Trans. Comput. Log.},
volume = {19},
number = {1},
pages = {1:1--1:26},
year = {2018},
url = {https://doi.org/10.1145/3157053},
doi = {10.1145/3157053},
timestamp = {Thu, 23 Sep 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/tocl/BeyersdorffCMS18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tocl/AtseriasLN16,
author = {Albert Atserias and
Massimo Lauria and
Jakob Nordstr{\"{o}}m},
title = {Narrow Proofs May Be Maximally Long},
journal = {{ACM} Trans. Comput. Log.},
volume = {17},
number = {3},
pages = {19},
year = {2016},
url = {https://doi.org/10.1145/2898435},
doi = {10.1145/2898435},
timestamp = {Mon, 13 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/tocl/AtseriasLN16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/BeyersdorffCMS16,
author = {Olaf Beyersdorff and
Leroy Chew and
Meena Mahajan and
Anil Shukla},
editor = {Nicolas Ollinger and
Heribert Vollmer},
title = {Are Short Proofs Narrow? {QBF} Resolution is not Simple},
booktitle = {33rd Symposium on Theoretical Aspects of Computer Science, {STACS}
2016, February 17-20, 2016, Orl{\'{e}}ans, France},
series = {LIPIcs},
volume = {47},
pages = {15:1--15:14},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2016},
url = {https://doi.org/10.4230/LIPIcs.STACS.2016.15},
doi = {10.4230/LIPICS.STACS.2016.15},
timestamp = {Thu, 23 Sep 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stacs/BeyersdorffCMS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BeyersdorffCMS15a,
author = {Olaf Beyersdorff and
Leroy Chew and
Meena Mahajan and
Anil Shukla},
title = {Are Short Proofs Narrow? {QBF} Resolution is not Simple},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR15-152}},
year = {2015},
url = {https://eccc.weizmann.ac.il/report/2015/152},
eprinttype = {ECCC},
eprint = {TR15-152},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BeyersdorffCMS15a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/AtseriasLN14,
author = {Albert Atserias and
Massimo Lauria and
Jakob Nordstr{\"{o}}m},
title = {Narrow Proofs May Be Maximally Long},
booktitle = {{IEEE} 29th Conference on Computational Complexity, {CCC} 2014, Vancouver,
BC, Canada, June 11-13, 2014},
pages = {286--297},
publisher = {{IEEE} Computer Society},
year = {2014},
url = {https://doi.org/10.1109/CCC.2014.36},
doi = {10.1109/CCC.2014.36},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/AtseriasLN14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/AtseriasLN14,
author = {Albert Atserias and
Massimo Lauria and
Jakob Nordstr{\"{o}}m},
title = {Narrow Proofs May Be Maximally Long},
journal = {CoRR},
volume = {abs/1409.2731},
year = {2014},
url = {http://arxiv.org/abs/1409.2731},
eprinttype = {arXiv},
eprint = {1409.2731},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/AtseriasLN14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/AtseriasLN14,
author = {Albert Atserias and
Massimo Lauria and
Jakob Nordstr{\"{o}}m},
title = {Narrow Proofs May Be Maximally Long},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR14-118}},
year = {2014},
url = {https://eccc.weizmann.ac.il/report/2014/118},
eprinttype = {ECCC},
eprint = {TR14-118},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/AtseriasLN14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/birthday/KirchnerKN13,
author = {Claude Kirchner and
H{\'{e}}l{\`{e}}ne Kirchner and
Fabrice Nahon},
editor = {Andrei Voronkov and
Christoph Weidenbach},
title = {Narrowing Based Inductive Proof Search},
booktitle = {Programming Logics - Essays in Memory of Harald Ganzinger},
series = {Lecture Notes in Computer Science},
volume = {7797},
pages = {216--238},
publisher = {Springer},
year = {2013},
url = {https://doi.org/10.1007/978-3-642-37651-1\_9},
doi = {10.1007/978-3-642-37651-1\_9},
timestamp = {Tue, 14 May 2019 10:00:52 +0200},
biburl = {https://dblp.org/rec/conf/birthday/KirchnerKN13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Berkholz12,
author = {Christoph Berkholz},
title = {On the Complexity of Finding Narrow Proofs},
booktitle = {53rd Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2012, New Brunswick, NJ, USA, October 20-23, 2012},
pages = {351--360},
publisher = {{IEEE} Computer Society},
year = {2012},
url = {https://doi.org/10.1109/FOCS.2012.48},
doi = {10.1109/FOCS.2012.48},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Berkholz12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1204-0775,
author = {Christoph Berkholz},
title = {On the complexity of finding narrow proofs},
journal = {CoRR},
volume = {abs/1204.0775},
year = {2012},
url = {http://arxiv.org/abs/1204.0775},
eprinttype = {arXiv},
eprint = {1204.0775},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1204-0775.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/Nordstrom09,
author = {Jakob Nordstr{\"{o}}m},
title = {Narrow Proofs May Be Spacious: Separating Space and Width in Resolution},
journal = {{SIAM} J. Comput.},
volume = {39},
number = {1},
pages = {59--121},
year = {2009},
url = {https://doi.org/10.1137/060668250},
doi = {10.1137/060668250},
timestamp = {Thu, 08 Jun 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/Nordstrom09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/birthday/GnaedigK07,
author = {Isabelle Gnaedig and
H{\'{e}}l{\`{e}}ne Kirchner},
editor = {Hubert Comon{-}Lundh and
Claude Kirchner and
H{\'{e}}l{\`{e}}ne Kirchner},
title = {Narrowing, Abstraction and Constraints for Proving Properties of Reduction
Relations},
booktitle = {Rewriting, Computation and Proof, Essays Dedicated to Jean-Pierre
Jouannaud on the Occasion of His 60th Birthday},
series = {Lecture Notes in Computer Science},
volume = {4600},
pages = {44--67},
publisher = {Springer},
year = {2007},
url = {https://doi.org/10.1007/978-3-540-73147-4\_3},
doi = {10.1007/978-3-540-73147-4\_3},
timestamp = {Tue, 14 May 2019 10:00:52 +0200},
biburl = {https://dblp.org/rec/conf/birthday/GnaedigK07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:journals/entcs/Lindblad08,
author = {Fredrik Lindblad},
editor = {Brigitte Pientka and
Carsten Sch{\"{u}}rmann},
title = {Higher-Order Proof Construction Based on First-Order Narrowing},
booktitle = {Proceedings of the Second International Workshop on Logical Frameworks
and Meta-Languages: Theory and Practice, LFMTP@CADE 2007, Bremen,
Germany, July 15, 2007},
series = {Electronic Notes in Theoretical Computer Science},
volume = {196},
pages = {69--84},
publisher = {Elsevier},
year = {2007},
url = {https://doi.org/10.1016/j.entcs.2007.09.018},
doi = {10.1016/J.ENTCS.2007.09.018},
timestamp = {Thu, 09 Feb 2023 11:15:18 +0100},
biburl = {https://dblp.org/rec/journals/entcs/Lindblad08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Nordstrom06,
author = {Jakob Nordstr{\"{o}}m},
editor = {Jon M. Kleinberg},
title = {Narrow proofs may be spacious: separating space and width in resolution},
booktitle = {Proceedings of the 38th Annual {ACM} Symposium on Theory of Computing,
Seattle, WA, USA, May 21-23, 2006},
pages = {507--516},
publisher = {{ACM}},
year = {2006},
url = {https://doi.org/10.1145/1132516.1132590},
doi = {10.1145/1132516.1132590},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Nordstrom06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR05-066,
author = {Jakob Nordstr{\"{o}}m},
title = {Narrow Proofs May Be Spacious: Separating Space and Width in Resolution},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR05-066}},
year = {2005},
url = {https://eccc.weizmann.ac.il/eccc-reports/2005/TR05-066/index.html},
eprinttype = {ECCC},
eprint = {TR05-066},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR05-066.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jacm/Ben-SassonW01,
author = {Eli Ben{-}Sasson and
Avi Wigderson},
title = {Short proofs are narrow - resolution made simple},
journal = {J. {ACM}},
volume = {48},
number = {2},
pages = {149--169},
year = {2001},
url = {https://doi.org/10.1145/375827.375835},
doi = {10.1145/375827.375835},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jacm/Ben-SassonW01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cade/Stuber01,
author = {J{\"{u}}rgen Stuber},
editor = {Rajeev Gor{\'{e}} and
Alexander Leitsch and
Tobias Nipkow},
title = {A Model-Based Completeness Proof of Extended Narrowing and Resolution},
booktitle = {Automated Reasoning, First International Joint Conference, {IJCAR}
2001, Siena, Italy, June 18-23, 2001, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {2083},
pages = {195--210},
publisher = {Springer},
year = {2001},
url = {https://doi.org/10.1007/3-540-45744-5\_15},
doi = {10.1007/3-540-45744-5\_15},
timestamp = {Tue, 14 May 2019 10:00:39 +0200},
biburl = {https://dblp.org/rec/conf/cade/Stuber01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/Ben-SassonW99,
author = {Eli Ben{-}Sasson and
Avi Wigderson},
title = {Short Proofs Are Narrow - Resolution Made Simple (Abstract)},
booktitle = {Proceedings of the 14th Annual {IEEE} Conference on Computational
Complexity, Atlanta, Georgia, USA, May 4-6, 1999},
pages = {2},
publisher = {{IEEE} Computer Society},
year = {1999},
url = {https://doi.org/10.1109/CCC.1999.766251},
doi = {10.1109/CCC.1999.766251},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/Ben-SassonW99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Ben-SassonW99,
author = {Eli Ben{-}Sasson and
Avi Wigderson},
editor = {Jeffrey Scott Vitter and
Lawrence L. Larmore and
Frank Thomson Leighton},
title = {Short Proofs are Narrow - Resolution Made Simple},
booktitle = {Proceedings of the Thirty-First Annual {ACM} Symposium on Theory of
Computing, May 1-4, 1999, Atlanta, Georgia, {USA}},
pages = {517--526},
publisher = {{ACM}},
year = {1999},
url = {https://doi.org/10.1145/301250.301392},
doi = {10.1145/301250.301392},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Ben-SassonW99.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR99-022,
author = {Eli Ben{-}Sasson and
Avi Wigderson},
title = {Short Proofs are Narrow - Resolution made Simple},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR99-022}},
year = {1999},
url = {https://eccc.weizmann.ac.il/eccc-reports/1999/TR99-022/index.html},
eprinttype = {ECCC},
eprint = {TR99-022},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR99-022.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/rta/Nieuwenhuis95,
author = {Robert Nieuwenhuis},
editor = {Jieh Hsiang},
title = {On Narrowing, Refutation Proofs and Constraints},
booktitle = {Rewriting Techniques and Applications, 6th International Conference,
RTA-95, Kaiserslautern, Germany, April 5-7, 1995, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {914},
pages = {56--70},
publisher = {Springer},
year = {1995},
url = {https://doi.org/10.1007/3-540-59200-8\_47},
doi = {10.1007/3-540-59200-8\_47},
timestamp = {Tue, 14 May 2019 10:00:46 +0200},
biburl = {https://dblp.org/rec/conf/rta/Nieuwenhuis95.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cade/Lysne94,
author = {Olav Lysne},
editor = {Alan Bundy},
title = {On the Connection between Narrowing and Proof by Consistency},
booktitle = {Automated Deduction - CADE-12, 12th International Conference on Automated
Deduction, Nancy, France, June 26 - July 1, 1994, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {814},
pages = {133--147},
publisher = {Springer},
year = {1994},
url = {https://doi.org/10.1007/3-540-58156-1\_10},
doi = {10.1007/3-540-58156-1\_10},
timestamp = {Tue, 14 May 2019 10:00:39 +0200},
biburl = {https://dblp.org/rec/conf/cade/Lysne94.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@incollection{DBLP:series/wsscs/HartmanisCRR93,
author = {Juris Hartmanis and
Richard Chang and
Desh Ranjan and
Pankaj Rohatgi},
editor = {Grzegorz Rozenberg and
Arto Salomaa},
title = {On {IP} = {PSPACE} and Theorems with Narrow Proofs},
booktitle = {Current Trends in Theoretical Computer Science - Essays and Tutorials},
series = {World Scientific Series in Computer Science},
volume = {40},
pages = {484--493},
publisher = {World Scientific},
year = {1993},
url = {https://doi.org/10.1142/9789812794499\_0036},
doi = {10.1142/9789812794499\_0036},
timestamp = {Tue, 14 Dec 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/series/wsscs/HartmanisCRR93.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
a service of 
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
retrieved on 2024-05-03 13:00 CEST from data curated by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
