File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Parity problem with a cellular automaton solution

TitleParity problem with a cellular automaton solution
Authors
Lee, KMXu, HChau, HF
KeywordsBinary Sequences
Boundary Conditions
Problem Solving
Theorem Proving
Issue Date2001
PublisherAmerican Physical Society. The Journal's web site is located at http://pre.aps.org
Citation
Physical Review E (Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics), 2001, v. 64 n. 2, article no. 026702 How to Cite?
DOI: http://dx.doi.org/10.1103/PhysRevE.64.026702
AbstractThe parity of a bit string of length N is a global quantity that can be efficiently computed using a global counter in O(N) time. But is it possible to find the parity using cellular automata with a set of local rule tables without using any global counter? Here, we report a way to solve this problem using a number of r=1 binary, uniform, parallel, and deterministic cellular automata applied in succession for a total of O(N2) time.
Persistent Identifierhttp://hdl.handle.net/10722/43328
ISSN
1063-651X
ISI Accession Number ID
WOS:000170493100102
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorLee, KMen_HK
dc.contributor.authorXu, Hen_HK
dc.contributor.authorChau, HFen_HK
dc.date.accessioned2007-03-23T04:43:40Z-
dc.date.available2007-03-23T04:43:40Z-
dc.date.issued2001en_HK
dc.identifier.citationPhysical Review E (Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics), 2001, v. 64 n. 2, article no. 026702-
dc.identifier.issn1063-651X-
dc.identifier.urihttp://hdl.handle.net/10722/43328-
dc.description.abstractThe parity of a bit string of length N is a global quantity that can be efficiently computed using a global counter in O(N) time. But is it possible to find the parity using cellular automata with a set of local rule tables without using any global counter? Here, we report a way to solve this problem using a number of r=1 binary, uniform, parallel, and deterministic cellular automata applied in succession for a total of O(N2) time.en_HK
dc.format.extent49787 bytes-
dc.format.extent28160 bytes-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypeapplication/msword-
dc.languageengen_HK
dc.publisherAmerican Physical Society. The Journal's web site is located at http://pre.aps.orgen_HK
dc.relation.ispartofPhysical Review E (Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics)-
dc.rightsCopyright 2001 by The American Physical Society. This article is available online at https://doi.org/10.1103/PhysRevE.64.026702-
dc.subjectBinary Sequencesen_HK
dc.subjectBoundary Conditions-
dc.subjectProblem Solving-
dc.subjectTheorem Proving-
dc.titleParity problem with a cellular automaton solutionen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1063-651X&volume=64&issue=2&spage=026702:1&epage=4&date=2001&atitle=Parity+problem+with+a+cellular+automaton+solutionen_HK
dc.identifier.authorityLee, KM=rp01471-
dc.identifier.authorityLee, KM=rp01471-
dc.description.naturepublished_or_final_versionen_HK
dc.identifier.doi10.1103/PhysRevE.64.026702en_HK
dc.identifier.scopuseid_2-s2.0-0035420843-
dc.identifier.hkuros64913-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0035420843&selection=ref&src=s&origin=recordpage-
dc.identifier.volume64-
dc.identifier.issue2-
dc.identifier.spagearticle no. 026702-
dc.identifier.epagearticle no. 026702-
dc.identifier.isiWOS:000170493100102-
dc.publisher.placeUnited States-
dc.identifier.scopusauthoridLee, KM=26659913500-
dc.identifier.scopusauthoridXu, H=8907566300-
dc.identifier.scopusauthoridChau, HF=7005742276-
dc.identifier.issnl1063-651X-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats