{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:39:40Z","timestamp":1753889980792,"version":"3.41.2"},"reference-count":13,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2012,6,1]],"date-time":"2012-06-01T00:00:00Z","timestamp":1338508800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>This paper discusses the topic of the minimum width of a regular resolution\nrefutation of a set of clauses. The main result shows that there are examples\nhaving small regular resolution refutations, for which any regular refutation\nmust contain a large clause. This forms a contrast with corresponding results\nfor general resolution refutations.<\/jats:p>","DOI":"10.2168\/lmcs-8(2:8)2012","type":"journal-article","created":{"date-parts":[[2013,9,23]],"date-time":"2013-09-23T14:50:43Z","timestamp":1379947843000},"source":"Crossref","is-referenced-by-count":3,"title":["Width and size of regular resolution proofs"],"prefix":"10.46298","volume":"Volume 8, Issue 2","author":[{"given":"Alasdair","family":"Urquhart","sequence":"first","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2012,6,1]]},"reference":[{"key":"10.2168\/LMCS-8(2:8)2012_alekjohpiturq2007","doi-asserted-by":"crossref","first-page":"81","DOI":"10.4086\/toc.2007.v003a005","volume":"3","author":"Michael Alekhnovich, Jan Johannsen, Toni","year":"2007","journal-title":"Theory of Computing"},{"key":"10.2168\/LMCS-8(2:8)2012_alonsp","unstructured":"Noga Alon and Joel H. Spencer.The Probabilistic Method. John Wiley, 1992."},{"key":"10.2168\/LMCS-8(2:8)2012_atseriasdalmau2008","unstructured":"Albert Atserias and Victor Dalmau. A combinatorial characterization of resolution width.Journal of Computer and System Sciences, 74:323-334, 2008. Preliminary version: 18th IEEE Conference on Computational Complexity, pp. 239-247, 2003."},{"key":"10.2168\/LMCS-8(2:8)2012_bensassonimpagliazzowigderson2004","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1007\/s00493-004-0036-5","volume":"24","author":"Eli Ben-Sasson, Russell Impagliazzo, and","year":"2004","journal-title":"Combinatorica"},{"key":"10.2168\/LMCS-8(2:8)2012_bens01","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1145\/375827.375835","volume":"48","author":"Eli Ben-Sasson and Avi Wigderson","year":"2001","journal-title":"Journal of the Association for Computing Machinery 48:149-169, 2001."},{"key":"10.2168\/LMCS-8(2:8)2012_bollobas1998","doi-asserted-by":"crossref","unstructured":"B\u00e9la Bollob\u00e1s.Modern Graph Theory. Springer-Verlag, 1998. Graduate Texts in Mathematics 184.","DOI":"10.1007\/978-1-4612-0619-4"},{"key":"10.2168\/LMCS-8(2:8)2012_kamathetal1995","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/rsa.3240070105","volume":"7","author":"Anil Kamath, Rajeev Motwani, Krishna Pal","year":"1995","journal-title":"Random Structures and Algorithms"},{"key":"10.2168\/LMCS-8(2:8)2012_mcdiarmid1998","doi-asserted-by":"crossref","unstructured":"Colin McDiarmid. Concentration. In Michel Habib, Colin McDiarmid, Jorge Ramirez-Alfonsin, and Bruce Reed, editors,Probabilistic Methods for Algorithmic Discrete Mathematics, pages 195-248. Springer, 1998. Algorithms and Combinatorics 16.","DOI":"10.1007\/978-3-662-12788-9_6"},{"key":"10.2168\/LMCS-8(2:8)2012_paulcelonitarjan1977","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1088\/0305-4470\/10\/2\/013","volume":"10","author":"W.J. Paul, R.E. Tarjan, and J.R. Celoni","year":"1977","journal-title":"Mathematical Systems Theory"},{"key":"10.2168\/LMCS-8(2:8)2012_sw","doi-asserted-by":"crossref","unstructured":"J\u00f6rg Siekmann and Graham Wrightson, editors.Automation of Reasoning. Springer-Verlag, New York, 1983.","DOI":"10.1007\/978-3-642-81955-1"},{"key":"10.2168\/LMCS-8(2:8)2012_ts70","doi-asserted-by":"crossref","unstructured":"G.S. Tseitin. On the complexity of derivation in propositional calculus. In A. O. Slisenko, editor,Studies in Constructive Mathematics and Mathematical Logic, Part 2, pages 115-125. Consultants Bureau, New York, 1970. Reprinted in sw, Vol. 2, pp. 466-483.","DOI":"10.1007\/978-1-4899-5327-8_25"},{"key":"10.2168\/LMCS-8(2:8)2012_urq95","doi-asserted-by":"crossref","first-page":"425","DOI":"10.2178\/bsl\/1203350879","volume":"1","author":"Alasdair Urquhart","year":"1995","journal-title":"The Bulletin of Symbolic Logic"},{"key":"10.2168\/LMCS-8(2:8)2012_urquhart2011","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1137\/090772897","volume":"40","author":"Alasdair Urquhart","year":"2011","journal-title":"SIAM Journal on Computing"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/862\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/862\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T19:57:59Z","timestamp":1681243079000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/862"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6,1]]},"references-count":13,"URL":"https:\/\/doi.org\/10.2168\/lmcs-8(2:8)2012","relation":{"references":[{"id-type":"doi","id":"10.1088\/0305-4470\/10\/2\/013","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"1205.1050","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1205.1050","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2012,6,1]]},"article-number":"862"}}