Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userColor Graphs: An Efficient Model For Two-Dimensional Cellular Automata Linear Rules
145
0
0.0
(
0
)
Added by
Sudhakar Sahoo
Publication date
2008
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Two-dimensional nine neighbor hood rectangular Cellular Automata rules can be modeled using many different techniques like Rule matrices, State Transition Diagrams, Boolean functions, Algebraic Normal Form etc. In this paper, a new model is introduced using color graphs to model all the 512 linear rules. The graph theoretic properties therefore studied in this paper simplifies the analysis of all linear rules in comparison with other ways of its study.
rate research
Read More
In this paper, we analyze the algebraic structure of some null boundary as well as some periodic boundary 2-D Cellular Automata (CA) rules by introducing a new matrix multiplication operation using only AND, OR instead of most commonly used AND, EX-OR. This class includes any CA whose rule, when written as an algebra, is a finite Abelean cyclic group in case of periodic boundary and a finite commutative cyclic monoid in case of null boundary CA respectively. The concept of 1-D Multiple Attractor Cellular Automata (MACA) is extended to 2-D. Using the family of 2-D MACA and the finite Abelian cyclic group, an efficient encompression algorithm is proposed for binary images.
In this paper, linear Cellular Automta (CA) rules are recursively generated using a binary tree rooted at 0. Some mathematical results on linear as well as non-linear CA rules are derived. Integers associated with linear CA rules are defined as linear numbers and the properties of these linear numbers are studied.
This paper deals with the theory and application of 2-Dimensional, nine-neighborhood, null- boundary, uniform as well as hybrid Cellular Automata (2D CA) linear rules in image processing. These rules are classified into nine groups depending upon the number of neighboring cells influences the cell under consideration. All the Uniform rules have been found to be rendering multiple copies of a given image depending on the groups to which they belong where as Hybrid rules are also shown to be characterizing the phenomena of zooming in, zooming out, thickening and thinning of a given image. Further, using hybrid CA rules a new searching algorithm is developed called Sweepers algorithm which is found to be applicable to simulate many inter disciplinary research areas like migration of organisms towards a single point destination, Single Attractor and Multiple Attractor Cellular Automata Theory, Pattern Classification and Clustering Problem, Image compression, Encryption and Decryption problems, Density Classification problem etc.
In the mid 80s, Lichtenstein, Pnueli, and Zuck proved a classical theorem stating that every formula of Past LTL (the extension of LTL with past operators) is equivalent to a formula of the form $bigwedge_{i=1}^n mathbf{G}mathbf{F} varphi_i vee mathbf{F}mathbf{G} psi_i$, where $varphi_i$ and $psi_i$ contain only past operators. Some years later, Chang, Manna, and Pnueli built on this result to derive a similar normal form for LTL. Both normalisation procedures have a non-elementary worst-case blow-up, and follow an involved path from formulas to counter-free automata to star-free regular expressions and back to formulas. We improve on both points. We present a direct and purely syntactic normalisation procedure for LTL yielding a normal form, comparable to the one by Chang, Manna, and Pnueli, that has only a single exponential blow-up. As an application, we derive a simple algorithm to translate LTL into deterministic Rabin automata. The algorithm normalises the formula, translates it into a special very weak alternating automaton, and applies a simple determinisation procedure, valid only for these special automata.
In this paper, we explore the two-dimensional behavior of cellular automata with shuffle updates. As a test case, we consider the evacuation of a square room by pedestrians modeled by a cellular automaton model with a static floor field. Shuffle updates are characterized by a variable associated to each particle and called phase, that can be interpreted as the phase in the step cycle in the frame of pedestrian flows. Here we also introduce a dynamics for these phases, in order to modify the properties of the model. We investigate in particular the crossover between low- and high-density regimes that occurs when the density of pedestrians increases, the dependency of the outflow in the strength of the floor field, and the shape of the queue in front of the exit. Eventually we discuss the relevance of these results for pedestrians.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
