File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Modulo three problem with a cellular automaton solution

TitleModulo three problem with a cellular automaton solution
Authors
Xu, HLee, KMChau, HF
KeywordsCellular automaton
Classifier system
Discrete dynamical system
Symbolic dynamics
Issue Date2003
PublisherWorld Scientific Publishing Co Pte Ltd. The Journal's web site is located at http://www.worldscinet.com/ijmpc/ijmpc.shtml
Citation
International Journal Of Modern Physics C, 2003, v. 14 n. 3, p. 249-256 How to Cite?
DOI: http://dx.doi.org/10.1142/S0129183103004450
AbstractAn important global property of a bit string is the number of ones in it. It has been found that the parity (odd or even) of this number can be found by a sequence of deterministic, translational invariant cellular automata with parallel update in succession for a total of O(N 2) time. In this paper, we discover a way to check if this number is divisible by three using the same kind of cellular automata in O(N 3) time. We also speculate that the method described here could be generalized to check if it is divisible by four and other positive integers.
Persistent Identifierhttp://hdl.handle.net/10722/80906
ISSN
0129-1831
2023 Impact Factor: 1.5
2023 SCImago Journal Rankings: 0.293
ISI Accession Number ID
WOS:000183573500001
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorXu, Hen_HK
dc.contributor.authorLee, KMen_HK
dc.contributor.authorChau, HFen_HK
dc.date.accessioned2010-09-06T08:11:34Z-
dc.date.available2010-09-06T08:11:34Z-
dc.date.issued2003en_HK
dc.identifier.citationInternational Journal Of Modern Physics C, 2003, v. 14 n. 3, p. 249-256en_HK
dc.identifier.issn0129-1831en_HK
dc.identifier.urihttp://hdl.handle.net/10722/80906-
dc.description.abstractAn important global property of a bit string is the number of ones in it. It has been found that the parity (odd or even) of this number can be found by a sequence of deterministic, translational invariant cellular automata with parallel update in succession for a total of O(N 2) time. In this paper, we discover a way to check if this number is divisible by three using the same kind of cellular automata in O(N 3) time. We also speculate that the method described here could be generalized to check if it is divisible by four and other positive integers.en_HK
dc.languageengen_HK
dc.publisherWorld Scientific Publishing Co Pte Ltd. The Journal's web site is located at http://www.worldscinet.com/ijmpc/ijmpc.shtmlen_HK
dc.relation.ispartofInternational Journal of Modern Physics Cen_HK
dc.subjectCellular automatonen_HK
dc.subjectClassifier systemen_HK
dc.subjectDiscrete dynamical systemen_HK
dc.subjectSymbolic dynamicsen_HK
dc.titleModulo three problem with a cellular automaton solutionen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0129-1831&volume=14&spage=249&epage=256&date=2003&atitle=Modulo+three+problem+with+a+cellular+automaton+solutionen_HK
dc.identifier.emailLee, KM: kmlee1@hkucc.hku.hken_HK
dc.identifier.emailChau, HF: hfchau@hku.hken_HK
dc.identifier.authorityLee, KM=rp01471en_HK
dc.identifier.authorityChau, HF=rp00669en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1142/S0129183103004450en_HK
dc.identifier.scopuseid_2-s2.0-0038463830en_HK
dc.identifier.hkuros77185en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0038463830&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume14en_HK
dc.identifier.issue3en_HK
dc.identifier.spage249en_HK
dc.identifier.epage256en_HK
dc.identifier.isiWOS:000183573500001-
dc.publisher.placeSingaporeen_HK
dc.identifier.scopusauthoridXu, H=8907566300en_HK
dc.identifier.scopusauthoridLee, KM=26659913500en_HK
dc.identifier.scopusauthoridChau, HF=7005742276en_HK
dc.identifier.issnl0129-1831-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats