{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,27]],"date-time":"2023-08-27T09:57:28Z","timestamp":1693130248379},"reference-count":8,"publisher":"World Scientific Pub Co Pte Lt","issue":"07","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2011,11]]},"abstract":"<jats:p> We design and implement highly parallel algorithms that use light as the tool of computation. Our computational laboratory consists of an ordinary xerox machine supplied with a box of transparencies. Our most basic operation is the evaluation of a Boolean function at arbitrarily many truth settings simultaneously. We find the maximum in a list of n-bit numbers of arbitrary length using at most n xerox copying steps. We count the number of elements in a list of arbitrary length of subsets of a given n-element set simultaneously in O(n<jats:sup>2<\/jats:sup>) copying steps. We decide, for any graph having n vertices and m edges, whether a 3-coloring exists in at most 2n + 4m copying steps. For large instances of problems such as the 3-color problem, this solution method may require the production of transparencies that display challengingly high densities of information. Our ultimate purpose here is to give hand tested 'ultra-parallel' algorithmic procedures that may provide useful suggestions for future technologies using light. <\/jats:p>","DOI":"10.1142\/s0129054111008921","type":"journal-article","created":{"date-parts":[[2011,12,2]],"date-time":"2011-12-02T15:02:15Z","timestamp":1322838135000},"page":"1625-1637","source":"Crossref","is-referenced-by-count":1,"title":["COMPUTING WITH LIGHT: TOWARD PARALLEL BOOLEAN ALGEBRA"],"prefix":"10.1142","volume":"22","author":[{"given":"TOM","family":"HEAD","sequence":"first","affiliation":[{"name":"Mathematical Sciences, Binghamton University, Binghamton, New York 13902-6000, USA"}]}],"member":"219","published-online":{"date-parts":[[2012,1,25]]},"reference":[{"key":"rf2","volume-title":"Computers and Intractability - A Guide to the Theory of NP- Completeness","author":"Garey M. R.","year":"1979"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626407003071"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88869-7_31"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14455-4_22"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-30296-4_20"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1364\/AO.31.003241"},{"key":"rf10","first-page":"57","volume":"6","author":"Oltean M.","journal-title":"Natural Computing"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-004-3379-3"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054111008921","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T18:49:18Z","timestamp":1565117358000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054111008921"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,11]]},"references-count":8,"journal-issue":{"issue":"07","published-online":{"date-parts":[[2012,1,25]]},"published-print":{"date-parts":[[2011,11]]}},"alternative-id":["10.1142\/S0129054111008921"],"URL":"https:\/\/doi.org\/10.1142\/s0129054111008921","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,11]]}}}