IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v10y2022i19p3541-d928317.html
   My bibliography  Save this article

Elementary Cellular Automata as Invariant under Conjugation Transformation or Combination of Conjugation and Reflection Transformations, and Applications to Traffic Modeling

Author

Listed:
  • Valery Kozlov

    (Steklov Mathematical Institute RAS, 119991 Moscow, Russia)

  • Alexander Tatashev

    (Department of Higher Mathematics, Faculty of Automobile Transport, Moscow Automobile and Road Construction State Technical University (MADI), 125139 Moscow, Russia
    Department of Cybernetics and Information Technologies, Faculty of Information Technologies, Moscow Technical University of Communications and Informatics, 123423 Moscow, Russia)

  • Marina Yashina

    (Russia and Moscow Aviation Institute (MAI), Moscow Automobile and Road Construction State Technical University (MADI), 125319 Moscow, Russia)

Abstract

This paper develops the analysis of properties of the cellular automata class introduced by the authors. It is assumed that the set of automaton cells is finite and forms a closed lattice, and there are two states for each automaton cell. We consider a new concept. This concept is the average velocity of a cellular automaton, which characterizes the average intensity of changes in the states of the automaton’s cells for a given initial state. The automaton velocity is equal to 1 if the state of any cell changes at each step. The spectrum of average velocities of a cellular automaton is the set of average velocities for different initial states. Since the state space is finite, the automaton, starting from a certain moment of time, is in periodically repeating states of a cycle, and thus, the research of the velocity spectrum is related to the problem of studying the set of the automaton cycles. For elementary cellular automata, the introduced class consists of a subclass of automata such that the conjugation trasformation of an automaton is the automaton itself (Subclass A) or the reflection of the automaton (Subclass B). For this class, it is proved that the spectrum of the automaton contains the value v 0 if and only if the spectrum of the complementary automaton contains the value 1 − v 0 (the sum of the index of elementary cellular automaton and the complementary automaton is 255). For automata of Subclasses A and B, the set of cycles and the velocity spectrum are studied. For Subclass A, a theorem has been proved such that in accordance with this theorem, if two automata complementary to each other start evolving in the same initial state, then the sum of their average velocities is equal to 1. This theorem for Subclass A is generalized to cellular automata, invariant under the conjugation transformation, of more general type than elementary automata. Generalizations of the theorem have been given for the class of one-dimensional cellular automata with a neighborhood containing 2 r + 1 cells (the next state of the cell depends on the present states of this cell, r cells on the left and r cells on the right) and for some traditionally considered classes of two-dimensional automata. Some elementary cellular automata belonging to the class considered in the paper can be interpreted as transport models. The properties of the spectra for these automata are studied and compared with the properties of elementary cellular automata not invariant under the considered transformations and can also be interpreted as transport models. The analytical results obtained for these simple models can be used to study the qualitative properties and limiting behavior of more complex transport models.

Suggested Citation

  • Valery Kozlov & Alexander Tatashev & Marina Yashina, 2022. "Elementary Cellular Automata as Invariant under Conjugation Transformation or Combination of Conjugation and Reflection Transformations, and Applications to Traffic Modeling," Mathematics, MDPI, vol. 10(19), pages 1-18, September.
  • Handle: RePEc:gam:jmathe:v:10:y:2022:i:19:p:3541-:d:928317
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/10/19/3541/pdf
    Download Restriction: no

    File URL: https://www.mdpi.com/2227-7390/10/19/3541/
    Download Restriction: no
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. George Cosmin Stănică & Petre Anghelescu, 2023. "Cryptographic Algorithm Based on Hybrid One-Dimensional Cellular Automata," Mathematics, MDPI, vol. 11(6), pages 1-17, March.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:10:y:2022:i:19:p:3541-:d:928317. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.