English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

A subset of the number conserving rules of binary two-dimensional cellular automata of unit radius in Moore’s neighbourhood is obtained. We relied on related concepts already described in the literature for von Neumann’s neighbourhood and for the elementary space of cellular automata, while making the necessary extensions. In doing so, algorithms were used for the creation of traffic rules and for the creation of two-dimensional rules with Moore’s neighbourhood of radius 1 derived from conservative one-dimensional rules with radius 4. All the constructed rules have been validated by implementing a known algorithm that establishes the presence of the conservation property of a rule. The approach is effective but the analysis of the constructed number conserving rules points at the necessity of developing further processes of rule construction. Resumo. Foi obtido um subconjunto das regras conservativas (number conserving) de autômatos celulares bidimensionais binários de raio unitário em vizinhança de Moore. Baseou-se em conceitos relacionados já descritos na literatura para a vizinhança de von Neumann e para o espaço elementar dos autômatos celulares, realizando-se as extensões necessárias. Nesse sentido, algoritmos foram usados para a criação de regras de tráfego e de regras bidimensionais com a vizinhança de Moore de raio 1 derivadas de regras unidimensionais conservativas de raio 4. Todas as regras construı́das foram validadas implementando-se um algoritmo existente que estabelece a presença da propriedade de conservação em uma regra. A abordagem é eficaz, mas a análise das regras construı́das que preservam a conservação numérica apontam para a necessidade de desenvolver novos processos de construção de regras. 1. Introdução Autômatos celulares (ACs) são sistemas dinâmicos discretos, desenvolvidos originalmente para modelar sistemas autorreplicantes [Von Neumann et al. 1966]. Tratam-se de sistemas onde todas as interações são locais e usualmente simples, mas com poder de descrever comportamentos complexos; estruturam-se em um reticulado regular de células, cujos estados, em quantidade finita, são alterados de forma sı́ncrona, a partir dos estados das células vizinhas [Wolfram 1994, Kari 2005]. Dependendo de como são definidos, podem possuir propriedades que ajudam a modelar fenômenos naturais, como leis de conservação de energia e massa [Pivato 2002], tal como fluxo discretizado de fluı́dos [Boon 1991] e tráfego de carros [Nagel and Schreckenberg 1992], entre outros. Nesses casos, o que os modelos citados têm em comum é a noção de conservabilidade, onde alguma propriedade do estado global do sistema se mantém ao longo do tempo, como a conservabilidade numérica (number conservation), em que a soma dos estados na configuração inicial do AC permanece constante. Como a conservabilidade numérica é o foco deste trabalho, para simplificar nos referimos à essa propriedade simplesmente por conservabilidade. Apesar de a noção de conservabilidade numérica em ACs ser um tema importante na área, os resultados já apresentados na literatura foram delimitados, majoritariamente, a espaços de regras unidimensionais, ou de regras bidimensionais com um tipo especı́fico de vizinhança, a de von Neumann, em contraste com o tipo de vizinhança de interesse aqui, que é a vizinhança bidimensional de Moore, ambas as quais serão definidas posteriormente. Assim, por exemplo, em [Boccara and Fukś 1998] foi mostrado como determinar todas as regras conservativas no espaço unidimensional binário de raio r = 1 e em [Boccara and Fukś 2002] extrapolou-se para casos unidimensionais, k-ários de vizinhança de tamanho arbitrário. Em [Durand et al. 2003] descreveuse a existência de três definições de conservabilidade (periódicas, finitas e infinitas) e provou-se a equivalência delas entre si. Também é demonstrado o que as regras devem respeitar para serem consideradas conservativas em dimensões d > 1 com vizinhança hiper-retangular. Em [Wolnik et al. 2017], foram apresentadas as condições necessárias e suficientes para que ACs de dimensões e de estados arbitrários em vizinhança de von Neumann sejam conservativos. Em [Wolnik and De Baets 2019a], foi provado que todos os ACs binários conservativos são intrinsecamente unidimensionais em vizinhança de von Neumann, independente de suas dimensões, isto é, sempre existirá 4d + 1 regras conservativas, sendo elas a identidade, os deslocamentos e as regras de tráfego. Em [Wolnik and De Baets 2019b], foi mostrado um novo método de estudo de reversibilidade em ACs conservativos k-ários d-dimensionais com vizinhança de von Neumann, utilizando-se do método da decomposição de regras por divisão e perturbação (split-andpertubation decomposition); nesse trabalho, o foco foi mostrar que ACs conservativos reversı́veis ternários d-dimensionais não são suficientes para decretar a existência de ACs não triviais com as caracterı́sticas citadas anteriormente. O objetivo do presente estudo é realizar uma análise exploratória do espaço de regras conservativas de ACs bidimensionais binários em vizinhança de Moore de raio unitário, aplicando ferramentas e conceitos já estabelecidos sobre outros tipos de vizinhança, mas adaptando-as convenientemente de forma que se possa atingir um certo nı́vel de exploração do espaço de interesse. Este artigo se estrutura da seguinte forma. A Seção 2 expõe os conceitos que servirão de base para o entendimento do restante do artigo. A Seção 3 mostra como as regras conservativas do espaço elementar serviram de inspiração para construir regras conservativas do espaço restrito desta pesquisa. Já a Seção 4 sugere uma heurı́stica para revelar regras conservativas no espaço bidimensional de vizinhança de Moore de raio unitário utilizando composição de regras unidimensionais. O artigo encerra com a Seção 5, fazendo uma crı́tica aos resultados obtidos e sugerindo possı́veis complementos futuros. 2. Referencial Teórico Esta seção apresenta os conceitos que sustentam a pesquisa, quais sejam, autômato celular (AC) e sua formalização matemática; conceito de vizinhança, principalmente em ACs bidimensionais; definição geral de conservabilidade e especı́fica para vizinhança m × n; equivalência dinâmica, seu significado e caracterização das operações em uma e duas dimensões; e, por fim, a noção de composição de regras unidimensionais. 2.1. Definições Básicas Autômatos celulares são quádruplas do tipo (d, S,N, f), onde d refere-se à dimensão espacial, com d ≥ 1; S é o conjunto dos possı́veis estados que as células podem assumir, com S = {0, 1, . . . , q − 1}; N = (~ a1, ~ a2, . . . , ~ an) é o vetor de vizinhança de tamanho n, sendo que, para casos unidimensionais, n = 2r + 1, onde r é o raio desta vizinhança; e f é a função de transição de estado, também chamada de regra local, sendo f : S → S [Durand et al. 2003, Moreira 2003, Kari 2005]. Configuração c : Z → S é uma função que mapeia o estado de todas as células em um passo de tempo t, e C é o conjunto de todas as configurações possı́veis para um determinado AC (c ∈ C). A função global F de um AC é dada por F : SZd → SZd , ou seja, é a função que representa a mudança de estado de todas as células dado um passo de tempo t. A representação temporal de uma função global f pode ser dada pelo número da regra Rf [Wolfram 1994], onde:

Exploração do Espaço de Regras Conservativas Binárias com Vizinhança de Moore