Made available in DSpace on 2016-03-15T19:37:45Z (GMT). No. of bitstreams: 1
Wander Lairson Costa.pdf: 1957133 bytes, checksum: 6819580d97bb5eaca5ea04352fcda0b8 (MD5)
Previous issue date: 2013-03-15 / Universidade Presbiteriana Mackenzie / Cellular automata are totally discrete systems that act locally in a simple and deterministic way, but whose resulting global behavior can be extremely complex. The set of possible global configurations in one finite time step for a CA can be described by a regular language, which in turn can be represented by a finite automaton, more precisely the so-called process graph, in which all states are initial and final. Here, we study the temporal evolution complexity of the elementary cellular automata (i.e., one-dimensional, binary, with radius 1), and related previous works are revisited and discussed, indicating problems and their consequences. We also start up a novel approach for the problem, substituting the process graph based representation that describes the configuration at each time step by adjacency matrices derived from them. In fact, we extend the classical adjacency matrix notation, as they cannot fully represent process graphs. With this new notation, we show that it is possible to obtain the algorithm to generate a process graph
for an arbitrary finite time step for each of the rules at study. In conclusion, although advancing the limit graph problem, it still remains open, and we provide suggestions for further research. / Autômatos celulares são sistemas totalmente discretos que agem localmente de forma simples e determinística, mas cujo comportamento global resultante pode ser extremamente
complexo. O conjunto de possíveis configurações globais em um passo de tempo t finito para um autômato celular pode ser descrito por uma linguagem regular, a qual por sua vez pode ser representada por meio de um autômato finito, mais precisamente, pelo chamado grafo de processo, em que todos os estados são iniciais e finais. Estuda-se aqui a complexidade da evolução temporal dos autômatos celulares elementares (i.e., unidimensionais, binários, de raio 1), e trabalhos anteriores são revisitados e discutidos, no quais apontam-se problemas e suas consequências. Também inicia-se uma nova abordagem para o problema, substituindo a representação dos grafos de processo que descrevem a configuração a cada passo de tempo por matrizes de adjacência deles derivadas. De fato, estende-se a notação clássica de matriz de adjacência, já que ela se mostra insuficiente para descrever completamente os grafos de processo em questão. Com essa nova notação, mostra-se que é possível obter o algoritmo que gere o grafo de processo de tempo t para cada uma das regras estudadas. Conclui-se que, embora houve avanços para o problema do grafo limite, este ainda permanece aberto, e sugestões para continuação da pesquisa são dadas.
| Identifer | oai:union.ndltd.org:IBICT/oai:tede.mackenzie.br:tede/1431 |
| Date | 15 March 2013 |
| Creators | Costa, Wander Lairson |
| Contributors | Oliveira, Pedro Paulo Balbi de, Silva, Leandro Nunes de Castro, Oliveira, Gina Maira Barbosa de |
| Publisher | Universidade Presbiteriana Mackenzie, Engenharia Elétrica, UPM, BR, Engenharia Elétrica |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações do Mackenzie, instname:Universidade Presbiteriana Mackenzie, instacron:MACKENZIE |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.003 seconds