Predslike 2D celičnih avtomatov

JERAS, IZTOK (author), Šter, Branko (mentor)

Medtem ko je računanje predslik 1D celičnih avtomatov dobro raziskan in podrobno dokumentiran problem, je to področje pri 2D celičnih avtomatih manj raziskano. Za 1D problem poznamo algoritme za štetje in izpis predslik s procesno zahtevnostjo linearno odvisno od velikosti problema. Možno je tudi določiti, ali je 1D celični avtomat reverzibilen in kakšen je regularen jezik vseh stanj brez predslik. Pri 2D problemu sicer poznamo nekaj algoritmov za iskanje predslik, vendar so slabo teoretično raziskani. Vemo tudi, da je problem reverzibilnosti 2D celičnih avtomatov na splošno neodločljiv. Mreža predslik, ki sem jo razvil za potrebe analize predslik 1D celičnih avtomatov, se je izkazala za praktično orodje pri razlagi algoritmov in pri dokazovanju njihove pravilnosti. Tukaj opišem, kako se mrežo predslik tvori za 2D celične avtomate. Če je bila ta mreža za 1D problem navaden graf, je za 2D problem razširjena v tretjo dimenzijo. Predslike so namesto poti v grafu ploskve na mreži. Robni pogoj se spremeni iz uteži za vozlišča, ki zaključujejo pot v 1D problemu, v uteži za sklenjeno pot okoli ploskve predslike v 2D problemu. Pri razvoju algoritma se je izkazalo, da štetja predslik 2D celičnega avtomata ni mogoče izvesti v linearni odvisnosti od velikosti problema. Zahtevnost podanega algoritma narašča eksponentno z velikostjo problema v eni dimenziji. Podani algoritem se ne razlikuje dosti od obstoječih. Celični avtomat razdeli na vrstice in išče predslike za posamezno vrstico od prve do zadnje. Vrstične rezultate nato združi v rešitev za celoten 2D problem. Podobno kakor pri algoritmu za 1D probleme, je analiza razdeljena v dva prehoda. V prvem prehodu po vrsticah algoritem prešteje predslike, v drugem opcijskem prehodu pa predslike izpiše. Drugi prehod poteka v obratni smeri kakor prvi prehod, tudi procesiranje posamezne vrstice poteka iz drugega zornega kota. Glavni napredek algoritma vidim v uporabi učinkovitih rešitev za 1D problem pri analizi vrstic ter v uporabi progresivnega kodiranja vmesnih rezultatov, kar lahko zmanjša porabo pomnilnika.

• Language: Slovenian
• Keywords: celični avtomati, predslike, predhodniki, računska zahtevnost, reverzibilnost, rajski vrt, Conwayeva igra življenja, trid, quad
• Work type: Master's thesis
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2016
• PID: 20.500.12556/RUL-85959
• Publication date in RUL: 30.09.2016

Secondary language

• Language: English
• Title: Preimages of 2D cellular automata

Abstract

While computing preimages of 1D cellular automata is a well researched and documented problem, for 2D cellular automata there is less research available. For the 1D problem we know algorithms for counting and listing preimages where computational complexity is a linear function of the size of the problem. It is possible to determine whether a 1D cellular automaton is reversible, and what is the Garden of Eden sequence regular language. For the 2D problem we know a few algorithms, but they are poorly theoretically researched. We also know that the reversibility problem is in general undecidable for 2D cellular automata. The preimage network, first developed for 1D cellular automata, was proved to be a useful tool for explaining algorithms and for constructing proofs. Here I explain how to construct the preimage network for 2D cellular automata. While for the 1D problem this network is a normal graph, for 2D it was extended into the third dimension. Preimages are transformed from paths in the graph in 1D into surfaces on the network in 2D. Edge conditions are transformed from weights for vertices ending a path in the 1D problem into weights for the closed path around a preimage surface in the 2D problem. While developing the algorithm, it proved impossible to count preimages of 2D cellular automata with processing requirements growing linearly with problem size. Instead, processing requirements grow exponentially with the size in one of the dimensions. The described algorithm does not differ much from the existing ones. The cellular automaton is split into rows, the preimage list is first determined for each row from the first to the last. The row results are then combined into the result for the whole 2D problem. In a similar fashion to the 1D approach, the algorithm splits into two passes. In the first pass preimages are counted, in the second optional pass preimages are listed. The second pass is performed in the opposite direction, while rows are also observed from the opposite side. I see the main advantage of the described algorithm in using existing solutions for row processing. Solutions proved to be effective in solving the 1D problem. Using progressive encoding of intermediate solutions also enables reducing memory consumption.

• Keywords: cellular automata, preimages, predecessors, ataviser, computational complexity, reversi- bility, Garden of Eden, Conway’s Game of Life, trid, quad