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
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, Nonlinear, And Soft Matter Physics), 2001, v. 64 n. 2, p. 026702:1-4 How to Cite?
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
2014 Impact Factor: 2.288
2015 SCImago Journal Rankings: 0.999
References

 

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, Nonlinear, And Soft Matter Physics), 2001, v. 64 n. 2, p. 026702:1-4en_HK
dc.identifier.issn1539-3755en_HK
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.rightsPhysical Review E (Statistical, Nonlinear, And Soft Matter Physics). Copyright © American Physical Society.en_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
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.publisher.placeUnited States-
dc.identifier.scopusauthoridLee, KM=26659913500-
dc.identifier.scopusauthoridXu, H=8907566300-
dc.identifier.scopusauthoridChau, HF=7005742276-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats