Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Parity problem with a cellular automaton solution.

K M Lee1, H Xu, H F Chau

  • 1Department of Physics, University of Hong Kong, Pokfulam Road, Hong Kong.

Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics
|August 11, 2001
PubMed
Summary

This study demonstrates how to compute bit string parity using cellular automata without a global counter. The method utilizes successive applications of local rule tables, achieving parity calculation in O(N^2) time.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

One-Shot Min-Entropy Calculation of Classical-Quantum States and Its Application to Quantum Cryptography.

Physical review letters·2025
Same author

Quantum and Classical Data Transmission through Completely Depolarizing Channels in a Superposition of Cyclic Orders.

Physical review letters·2021
Same author

Differential-phase-shift quantum key distribution using heralded narrow-band single photons.

Optics express·2013
Same author

Incorporating inertia into multiagent systems.

Physical review. E, Statistical, nonlinear, and soft matter physics·2006
Same author

Memory is relevant in the symmetric phase of the minority game.

Physical review. E, Statistical, nonlinear, and soft matter physics·2005
Same author

Wealth inequality in the minority game.

Physical review. E, Statistical, nonlinear, and soft matter physics·2005

Area of Science:

  • Computer Science
  • Theoretical Computer Science
  • Cellular Automata

Background:

  • The parity of a bit string is a global property, typically computed efficiently using a global counter in linear time.
  • Calculating parity without global information presents a significant challenge in computational theory.

Purpose of the Study:

  • To investigate the possibility of computing bit string parity using only local rules within a cellular automaton framework.
  • To develop a method that avoids the use of a global counter for parity computation.

Main Methods:

  • The study employs a series of r=1 binary, uniform, parallel, and deterministic cellular automata.
  • These automata are applied sequentially to the bit string to derive the parity.

Main Results:

Related Experiment Videos

  • A novel method for computing bit string parity using cellular automata has been successfully developed.
  • The proposed method achieves the computation in a total time complexity of O(N^2).

Conclusions:

  • It is possible to compute the parity of a bit string using cellular automata with local rules, without relying on a global counter.
  • The developed cellular automata approach provides an alternative method for parity computation, albeit with a higher time complexity than global counters.