{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,26]],"date-time":"2026-05-26T23:05:44Z","timestamp":1779836744152,"version":"3.53.1"},"reference-count":2,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2011,1,5]],"date-time":"2011-01-05T00:00:00Z","timestamp":1294185600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Funct. Prog."],"published-print":{"date-parts":[[2011,3]]},"abstract":"<jats:p>\n                    The other day, over a very pleasant lunch in the restaurant of Oxford's recently renovated Ashmolean Museum, Oege de Moor gave me a problem about rectangles. The problem is explained more fully later, but roughly speaking one is given a finite set of rectangles\n                    <jats:italic>RS<\/jats:italic>\n                    and a rectangle\n                    <jats:italic>R<\/jats:italic>\n                    completely covered by\n                    <jats:italic>RS<\/jats:italic>\n                    . The task is to construct a single rectangle covering\n                    <jats:italic>R<\/jats:italic>\n                    among the elements of a larger set of rectangles associated with\n                    <jats:italic>RS<\/jats:italic>\n                    , called the\n                    <jats:italic>saturation<\/jats:italic>\n                    of\n                    <jats:italic>RS<\/jats:italic>\n                    . The saturation of\n                    <jats:italic>RS<\/jats:italic>\n                    is the closure of\n                    <jats:italic>RS<\/jats:italic>\n                    under so-called\n                    <jats:italic>consensus<\/jats:italic>\n                    operations, a term coined in (Quine, 1959), in which two rectangles are combined in two distinct ways to form new rectangles. The rectangle problem is a simplified version of containment-checking, a crucial component in a type inference algorithm for Datalog programs (Sch\u00e4fer &amp; de Moor, 2010). 19 In the Sch\u00e4fer-de Moor algorithm the problem is generalised to cubes in\n                    <jats:italic>n<\/jats:italic>\n                    -space rather than rectangles in two-space, the components of each cube are given by propositional formulae rather than by intervals on the real line, and certain equality and inhabitation constraints are taken into account. Oege felt that the central proof, Lemma 15 in (Sch\u00e4fer &amp; de Moor, 2010), deserved to be simplified so he posed the rectangle problem as a special case. This pearl was composed in response to the challenge.\n                  <\/jats:p>","DOI":"10.1017\/s0956796810000316","type":"journal-article","created":{"date-parts":[[2011,1,5]],"date-time":"2011-01-05T10:10:45Z","timestamp":1294222245000},"page":"119-128","source":"Crossref","is-referenced-by-count":0,"title":["Building a consensus: A rectangle covering problem"],"prefix":"10.1017","volume":"21","author":[{"given":"RICHARD S.","family":"BIRD","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2011,1,5]]},"reference":[{"key":"S0956796810000316_ref2","first-page":"145","article-title":"Type inference for datalog with complex type hierarchies","volume":"45","author":"Sch\u00e4fer","year":"2010","journal-title":"Princ. Program. Lang. 2010. ACM SIGPLAN Not."},{"key":"S0956796810000316_ref1","doi-asserted-by":"publisher","DOI":"10.2307\/2310460"}],"container-title":["Journal of Functional Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0956796810000316","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,26]],"date-time":"2026-05-26T22:36:23Z","timestamp":1779834983000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0956796810000316\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1,5]]},"references-count":2,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,3]]}},"alternative-id":["S0956796810000316"],"URL":"https:\/\/doi.org\/10.1017\/s0956796810000316","relation":{},"ISSN":["0956-7968","1469-7653"],"issn-type":[{"value":"0956-7968","type":"print"},{"value":"1469-7653","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1,5]]}}}