We study cellular automata as discrete dynamical systems and in particular investigate under which conditions two cellular automata are topologically conjugate. Based on work of McKinsey, Tarski, Pierce and Head we introduce derivative algebras to study the topological structure of sofic shifts in dimension one. This allows us to classify periodic cellular automata on sofic shifts up to topological conjugacy based on the structure of their periodic points. We also get new conjugacy invariants in the general case. Based on a construction by Hanf and Halmos, we construct a pair of non-homeomorphic subshifts whose disjoint sums with themselves are homeomorphic. From this we can construct two cellular automata on homeomorphic state spaces for which all points have minimal period two, which are, however, not topologically conjugate. We apply our methods to classify the 256 elementary cellular automata with radius one over the binary alphabet up to topological conjugacy. By means of linear algebra over the field with two elements and identities between Fibonacci-polynomials we show that every conjugacy between rule 90 and rule 150 cannot have only a finite number of local rules. Finally, we look at the sequences of finite dynamical systems obtained by restricting cellular automata to spatially periodic points. If these sequences are termwise conjugate, we call the cellular automata conjugate on all tori. We then study the invariants under this notion of isomorphism. By means of an appropriately defined entropy, we can show that surjectivity is such an invariant.

In recent years, texture synthesis has been a heated topic in computer graphics, and the development of advanced algorithms for generating high-quality 3D textures is an area of active research. A recently proposed model, Neural Cellular Automata, can synthesize realistic 2D texture images or videos. However, due to the complexity and non-differentiable nature of 3D rendering and the lack of definition of the neighborhood on 3D mesh objects, no one has extended the 2D Neural Cellular Automata to the 3D scenario. In this master’s thesis, we propose a novel method for modeling the neighborhood relationship on 3D mesh objects, drawing inspiration from a graph variant of the Neural Cellular Automata. We also design an end-to-end 3D texture synthesis pipeline, leveraging a differentiable renderer to enable the Graph Neural Cellular Automata to learn to synthesize desired 3D textures. Our method allows users to either give the text description of the target textures or present the target texture images as the objectives. We evaluate the effectiveness of our proposed method both qualitatively and quantitatively, comparing it with the state-of-the-art method to demonstrate that it achieves comparable or better results. Furthermore, we explore the homology between the graph variant of Neural Cellular Automata and the 2D model, examining whether our proposed model preserves critical properties of the 2D model such as zero-shot generalization and self-regeneration. Finally, we analyze the limitations and potential drawbacks of our proposed method and suggest directions for future research. In summary, this thesis proposes a novel approach to synthesizing high-quality 3D textures using the Graph Neural Cellular Automata model and a differentiable renderer. Our work provides a foundation for future research in this area, and we believe that our findings will contribute to the development of advanced algorithms for 3D texture synthesis. / Under de senaste åren har textursyntes varit ett hett ämne inom datorgrafik, och utvecklingen av avancerade algoritmer för att generera högkvalitativa 3D-texturer är ett aktivt forskningsområde. En nyligen föreslagen modell, Neural Cellular Automata, kan syntetisera realistiska 2D-texturbilder eller videor. Dock, på grund av komplexiteten och den icke-differentierbara naturen av 3D-rendering och bristen på definition av grannskapet på 3D-meshobjekt, har ingen utvidgat 2D Neural Cellular Automata till 3D-scenariot. I den här masteruppsatsen föreslår vi en ny metod för att modellera grannskapsrelationen på 3D-meshobjekt, inspirerade av en grafvariant av Neural Cellular Automata. Vi utformar också en ände-till-ände 3D-textursyntes pipeline, genom att utnyttja en differentierbar renderer för att möjliggöra för Graph Neural Cellular Automata att lära sig syntetisera önskade 3D-texturer. Vår metod tillåter användare att antingen ge textbeskrivningen av måltexturerna eller presentera måltexturbilderna som målen. Vi utvärderar effektiviteten av vår föreslagna metod både kvalitativt och kvantitativt, jämför den med den mest avancerade metoden för att visa att den uppnår jämförbara eller bättre resultat. Dessutom utforskar vi homologin mellan grafvarianten av Neural Cellular Automata och 2D-modellen, undersöker om vår föreslagna modell bevarar kritiska egenskaper hos 2D-modellen som zero-shot generalisering och självregenerering. Slutligen analyserar vi begränsningarna och eventuella nackdelar med vår föreslagna metod och föreslår riktningar för framtida forskning. Sammanfattningsvis föreslår denna avhandling en ny metod för att syntetisera högkvalitativa 3D-texturer med hjälp av Graph Neural Cellular Automata-modellen och en differentierbar renderer. Vårt arbete ger en grund för framtida forskning inom detta område, och vi tror att våra fynd kommer att bidra till utvecklingen av avancerade algoritmer för 3D-textursyntes.

No description available.

Les zones humides sont écosystèmes reconnus de vitale importance pour la conservation de la biodiversité et pour un développement soutenable. En Colombie, 26 % du territoire continental national est couvert de ces écosystèmes. Le complexe de zones humides urbaines de Bogota, en fait partie, avec 15 écosystèmes, dont la Convention Ramsar reconnaît 11. Ils sont uniques et jouent un rôle important dans l’approvisionnement des services écosystèmes à la zone urbaine. Cependant, ces écosystèmes urbains font face à de nombreux défis en raison de leur emplacement. Les causes et les conséquences de leur transformation sont très complexes. En appliquant des approches des systèmes complexes, sa dynamique de changement peut être étudiée. Les automates cellulaires sont l’une des techniques largement utilisées dans la modélisation de la dynamique spatiotemporelle des changements de l’usage et de l’occupation des sols. Cette étude propose l’analyse et la simulation des zones humides urbaines en appliquant une approche hybride par un modèle couplé de chaîne de Markov, de réseaux de neurones artificiels et d’automates cellulaires, afin d’estimer leurs changements d’étendue pour les années 2016, 2022, 2028 et 2034 dans la ville de Bogota, en Colombie. Pour extraire le changement d’occupation et d’utilisation du sol, trois images analogues des années 1998, 2004 et 2010 ont été a utilisées. Les résultats ont montré une diminution de 0,30 % de la couverture des zones humides en douze ans. De plus, les résultats suggèrent que la couverture des zones humides représentera 1,97 % de la zone d’étude totale en 2034, représentant une probabilité de diminution de 14 % en 24 ans. D’ailleurs, en appliquant l’analyse d’intensité, il a été constaté que le gain de cultures et de pâturages cible la perte de zones humides. Bien dont ces écosystèmes soient protégés et d’utilisation restreinte, leur patron de réduction se poursuivra en 2034. La pertinence de ce projet réside dans sa contribution potentielle au processus décisionnel au sein de la ville et en tant qu’instrument de gestion des ressources naturelles. En outre, les résultats de cette étude pourraient aider à atteindre l’objectif de développement durable 6 « Eau propre et assainissement » et l’atténuation du changement climatique. / Wetlands are ecosystems recognized as being of vital importance for the conservation of biodiversity and for sustainable development. In Colombia, 26% of the national continental territory is covered by these ecosystems. The complex of urban wetlands of Bogota is one of them, with 15 ecosystems, of which the Ramsar Convention recognizes 11. They are unique and play an important role in providing ecosystem services to the urban area. However, these urban ecosystems face many challenges due to their location. The causes and consequences of their transformation are very complex. By applying complex systems approaches, the dynamics of change can be studied. Cellular automata is one of the widely used techniques in modeling the spatiotemporal dynamics of land use and land cover changes. This study proposes the analysis and simulation of urban wetlands by applying a hybrid approach through a coupled model of the Markov chain, artificial neural networks, and cellular automata, in order to estimate the extent of changes for the years 2016, 2022, 2028, and 2034 in the city of Bogota, Colombia. To extract the change in land cover and land use, three analogous images from the years 1998, 2004, and 2010 were used. The results showed a 0.30% decrease in wetland coverage in twelve years. Furthermore, the results suggest that wetland cover will be 1.97% of the total study area in 2034, representing a 14% probability of a decrease in 24 years. Moreover, by applying the intensity analysis, it was found that the gain of crop and pastureland targets the loss of wetlands. Although these ecosystems are protected and of limited use, their pattern of reduction will continue in 2034. The relevance of this project lies in its potential contribution to decision-making within the city and as a natural resource management tool. In addition, the results of this study could help achieve Sustainable Development Goal 6 “Clean Water and Sanitation” and climate change mitigation.

No description available.

No description available.

O Dilema do Prisioneiro (DP) é o jogo mais proeminente da Teoria dos Jogos devido à emergência da cooperação entre jogadores egoístas. O comportamento de cada jogador depende da estratégia que ele adotada e do seu ganho, que é determinado em função dos parâmetros do DP (T, R, P e S) e do número z de vizinhos com que ele joga. Portanto, a estrutura espacial dos jogadores não é relevante. Em nosso trabalho, utilizamos um autômato celular unidimensional onde cada jogador pode cooperar ou desertar ao interagir, simetricamente, com seus z vizinhos mais próximos. O sistema proposto nos permitiu realizar um estudo exaustivo do espaço de parâmetros para as estratégias evolucionárias Darwiniana (EED) e a Pavloviana (EEP) e compara-las. A geometria unidimensional nos possibilita obter os mesmos resultados dos sistemas em dimensionalidade arbitrária d, além de apresentar várias vantagens em relação a elas. No sistema que propomos os efeitos de borda são menores, exige menos tempo para a execução das simulações numéricas, permite variar o valor de z e é fácil obter uma representação visual da evolução temporal do sistema. Tal visualização simplifica a compreensão das interações entre os jogadores, pois surgem padrões nos agrupamentos de cooperadores/desertores, semelhantes aos pertencentes às classes dos autômatos celulares elementares. O estudo destes padrões nos permite compreender simplesmente a emergência da cooperação ou deserção nos sistemas. A evolução temporal do sistema que adota a EED gera um diagrama de fases muito rico com a presença das fases cooperadora, desertora e caótica. Já para a EEP, obtivemos um novo resultado analítico para as transições de fase, que neste caso são: cooperadora e quasi-regular. O estudo numérico exaustivo determinou as regiões do espaço de parâmetros onde acontecem cada uma das fases, e os efeitos da auto-interação podendo assim validar os resultados teóricos. O estudo do caso particular T = 1, tradicionalmente considerado como trivial, mostrou que ele apresenta comportamentos inusitados. Nossa principal contribuição para o estudo do DP é a obtenção de um novo paradigma. A geometria unidimensional com interação de vizinhos simétricos permitiu a visualização da evolução de padrões de cooperadores e desertores, o cálculo analítico de Tc para a EEP e o estudo de T = 1 para tais sistemas. / The Prisoner Dilemma (PD) is the most prominent game of the Game Theory due to emergency of the cooperation between selfish players. The behavior of each player depends on his/her strategy and the payoff, which is determined in function of the PD parameters (T, R, P and S) and by the number z of neighbors with whom he/she plays. Therefore, the spatial structure of the players does not matter. In our work, we have used a one-dimensional cellular automaton where each player can cooperate or defect when interacting, symmetrically, with his/her z nearest neighbors. The considered system allowed us to carry out an exhaustive exploration of the parameters space for the Darwinian Evolutionary Strategy (EED) and Pavlovian (EEP) and compares them. One-dimensional geometry makes possible to us get the same results of the systems in arbitrary d dimensional networks, besides, it presents some advantages. For the system that we proposed compared to the others dimensional networks, the boundary effects are less present, it needs less time for run the numerical simulations, it allows to vary the z value and is easier to get the visual representation of the system temporal evolution. Such visualization simplifies the understanding of the interactions between the players, therefore patterns appear in the clusters of cooperator/defectors, and these patterns belong to the elementary cellular automata classes. The study of these patterns allows them to understand in an easy way the emergence of the cooperation or defection in the systems. The temporal evolution of the system that adopts the EED yields a very rich phases diagram with the presence of cooperative, defective and chaotic phases. By the other hand, for the EEP, we have got a new analytical result for the phase transitions that in this case are: quasi-regular and cooperative. The exhaustive exploration study determines the regions on the parameters space where happen each phases occurs, and the effect of the self-interaction and thus validate the theoretical results. The study of the particular case T = 1, traditionally considered as trivial one, showed that it presents unusual behaviors, that we will present. Our main contribution for the study of the DP is the attainment of a new paradigm. One-dimensional geometry with interaction of symmetrical neighbors allowed to visualizes the evolution of cooperators and defectors patterns, the analytical result for Tc for the EEP and the study of T = 1 for such systems.

Un automate cellulaire probabiliste (ACP) est une chaîne de Markov sur un espace symbolique. Le temps est discret, les cellules évoluent de manière synchrone, et le nouvel état de chaque cellule est choisi de manière aléatoire, indépendamment des autres cellules, selon une distribution déterminée par les états d'un nombre fini de cellules situées dans le voisinage. Les ACP sont utilisés en informatique comme modèle de calcul, ainsi qu'en biologie et en physique. Ils interviennent aussi dans différents contextes en probabilités et en combinatoire. Un ACP est ergodique s'il a une unique mesure invariante qui est attractive. Nous prouvons que pour les AC déterministes, l'ergodicité est équivalente à la nilpotence, ce qui fournit une nouvelle preuve de l'indécidabilité de l'ergodicité pour les ACP. Alors que la mesure invariante d'un AC ergodique est triviale, la mesure invariante d'un ACP ergodique peut être très complexe. Nous proposons un algorithme pour échantillonner parfaitement cette mesure. Nous nous intéressons à des familles spécifiques d'ACP, ayant des mesures de Bernoulli ou des mesures markoviennes invariantes, et étudions les propriétés de leurs diagrammes espace-temps. Nous résolvons le problème de classification de la densité sur les grilles de dimension supérieure ou égale à 2 et sur les arbres. Enfin, nous nous intéressons à d'autres types de problèmes. Nous donnons une caractérisation combinatoire des mesures limites pour des marches aléatoires sur des produits libres de groupes. Nous étudions les mesures d'entropie maximale de sous-décalages de type fini sur les réseaux et sur les arbres. Les ACP interviennent à nouveau dans ce dernier travail.

Les changements climatiques ont des impacts considérables sur le temps, les océans et les rivages, la vie sauvage. Ils amènent des problèmes désormais considérés comme majeurs par les gouvernements et organisations internationales. Ces efforts ont fourni un cadre à cette thèse, qui propose de procéder en boucle fermée de l’observation d’insectes ravageurs, avec des centaines de capteurs en réseau ("light traps"), au système d’information, et enfin à des décisions de lutte, manuelles ou automatiques. Le point d’appui pratique est la conception d’un système de comptage d’insectes proliférant dans les cultures de riz (BPH). L’abstraction que nous développons est celle d’une machine environnementale de grande taille, distribuée, qui capte et synthétise l’information, élabore des connaissances, et prend des décisions. Autour de cette abstraction, nous avons élaboré un système de vision "fisheye" effectuant le comptage des insectes. Nous proposons un système d’information géographique directement connecté au réseau de capteurs. Le couplage direct, "cyber-physique", entre les systèmes d’information et l’observation de l’environnement à échelle régionale est une nouveauté transposable, qui permet de comprendre et contrôler quantité d’évolutions. / Climate changes bring problems related to nature evolutions. Global warming has an impact on sea level, weather patterns, and wild life. A number of national and international organizations are developing research programs in these directions, including threats on cultures and insect proliferation. Monitoring these phenomena, observing consequences, elaborating counteracted strategies are critical for the economy and society.The initial motivation of this work was the understanding of change impacts in the Mekong Delta region. From there, automatic observation tools were designed with a real time information system able to integrate environmental measures, then to support knowledge production.Tracking environment evolutions is distributed sensing, which can be the association of efficient sensors and radio communications, operated under the control of an information system. Sensing insects is very complex due to their diversity and dispersion. However, this is feasible in the case of intensive agricultural production as it is the case of rice, having a small number of pests. An automatic vision observatory is proposed to observe the main threats for the rice, as an evolution of manual light traps. Radio communication weaves these observatories into a network with connection to databases storing measures and possible counteractions. An example observatory has a fisheye camera and insect counting algorithms for the BPH practical case in Vietnam.By considering the observation system as an input for an abstract machine, and considering decision and actions taken as a possible control on the environment, we obtain a framework for knowledge elaboration that can be useful in lots of other situations.

O Dilema do Prisioneiro (DP) é o jogo mais proeminente da Teoria dos Jogos devido à emergência da cooperação entre jogadores egoístas. O comportamento de cada jogador depende da estratégia que ele adotada e do seu ganho, que é determinado em função dos parâmetros do DP (T, R, P e S) e do número z de vizinhos com que ele joga. Portanto, a estrutura espacial dos jogadores não é relevante. Em nosso trabalho, utilizamos um autômato celular unidimensional onde cada jogador pode cooperar ou desertar ao interagir, simetricamente, com seus z vizinhos mais próximos. O sistema proposto nos permitiu realizar um estudo exaustivo do espaço de parâmetros para as estratégias evolucionárias Darwiniana (EED) e a Pavloviana (EEP) e compara-las. A geometria unidimensional nos possibilita obter os mesmos resultados dos sistemas em dimensionalidade arbitrária d, além de apresentar várias vantagens em relação a elas. No sistema que propomos os efeitos de borda são menores, exige menos tempo para a execução das simulações numéricas, permite variar o valor de z e é fácil obter uma representação visual da evolução temporal do sistema. Tal visualização simplifica a compreensão das interações entre os jogadores, pois surgem padrões nos agrupamentos de cooperadores/desertores, semelhantes aos pertencentes às classes dos autômatos celulares elementares. O estudo destes padrões nos permite compreender simplesmente a emergência da cooperação ou deserção nos sistemas. A evolução temporal do sistema que adota a EED gera um diagrama de fases muito rico com a presença das fases cooperadora, desertora e caótica. Já para a EEP, obtivemos um novo resultado analítico para as transições de fase, que neste caso são: cooperadora e quasi-regular. O estudo numérico exaustivo determinou as regiões do espaço de parâmetros onde acontecem cada uma das fases, e os efeitos da auto-interação podendo assim validar os resultados teóricos. O estudo do caso particular T = 1, tradicionalmente considerado como trivial, mostrou que ele apresenta comportamentos inusitados. Nossa principal contribuição para o estudo do DP é a obtenção de um novo paradigma. A geometria unidimensional com interação de vizinhos simétricos permitiu a visualização da evolução de padrões de cooperadores e desertores, o cálculo analítico de Tc para a EEP e o estudo de T = 1 para tais sistemas. / The Prisoner Dilemma (PD) is the most prominent game of the Game Theory due to emergency of the cooperation between selfish players. The behavior of each player depends on his/her strategy and the payoff, which is determined in function of the PD parameters (T, R, P and S) and by the number z of neighbors with whom he/she plays. Therefore, the spatial structure of the players does not matter. In our work, we have used a one-dimensional cellular automaton where each player can cooperate or defect when interacting, symmetrically, with his/her z nearest neighbors. The considered system allowed us to carry out an exhaustive exploration of the parameters space for the Darwinian Evolutionary Strategy (EED) and Pavlovian (EEP) and compares them. One-dimensional geometry makes possible to us get the same results of the systems in arbitrary d dimensional networks, besides, it presents some advantages. For the system that we proposed compared to the others dimensional networks, the boundary effects are less present, it needs less time for run the numerical simulations, it allows to vary the z value and is easier to get the visual representation of the system temporal evolution. Such visualization simplifies the understanding of the interactions between the players, therefore patterns appear in the clusters of cooperator/defectors, and these patterns belong to the elementary cellular automata classes. The study of these patterns allows them to understand in an easy way the emergence of the cooperation or defection in the systems. The temporal evolution of the system that adopts the EED yields a very rich phases diagram with the presence of cooperative, defective and chaotic phases. By the other hand, for the EEP, we have got a new analytical result for the phase transitions that in this case are: quasi-regular and cooperative. The exhaustive exploration study determines the regions on the parameters space where happen each phases occurs, and the effect of the self-interaction and thus validate the theoretical results. The study of the particular case T = 1, traditionally considered as trivial one, showed that it presents unusual behaviors, that we will present. Our main contribution for the study of the DP is the attainment of a new paradigm. One-dimensional geometry with interaction of symmetrical neighbors allowed to visualizes the evolution of cooperators and defectors patterns, the analytical result for Tc for the EEP and the study of T = 1 for such systems.