{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,6]],"date-time":"2025-08-06T12:54:37Z","timestamp":1754484877808},"reference-count":8,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2003,6]]},"abstract":"<jats:p> Block sorting is used in connection with Optical Character Recognition (OCR). Recent work has focused on finding good strategies which work in practice. In this paper, we show that optimizing block sorting is [Formula: see text]-hard. Along with this result, we give new non-trivial lower bounds. These bound can be computed efficiently. We define the concept of \"Local Property Algorithms\" and show that several previously published block sorting algorithms fall into this class. <\/jats:p>","DOI":"10.1142\/s0129054103001820","type":"journal-article","created":{"date-parts":[[2003,7,24]],"date-time":"2003-07-24T11:23:50Z","timestamp":1059045830000},"page":"425-437","source":"Crossref","is-referenced-by-count":13,"title":["Block Sorting is Hard"],"prefix":"10.1142","volume":"14","author":[{"given":"Wolfgang W.","family":"Bein","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Nevada, Las Vegas, NV 89154, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lawrence L.","family":"Larmore","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Nevada, Las Vegas, NV 89154, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shahram","family":"Latifi","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of Nevada, Las Vegas, NV 89154, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"I. Hal","family":"Sudborough","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Unversity of Texas at Dallas, Richardson, TX 75083, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019528280X"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793250627"},{"key":"rf4","volume-title":"Computers and intractability \u2013 A guide to the theory of NP-completeness","author":"Garey M. R.","year":"1979"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(79)90068-2"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(98)00072-9"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010041"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0874"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1109\/34.368146"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054103001820","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:38:23Z","timestamp":1565138303000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054103001820"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,6]]},"references-count":8,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2003,6]]}},"alternative-id":["10.1142\/S0129054103001820"],"URL":"https:\/\/doi.org\/10.1142\/s0129054103001820","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,6]]}}}