Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
Cellular automata over generalized Cayley graphs
View through CrossRef
It is well-known that cellular automata can be characterized as the set of translation-invariant continuous functions over a compact metric space; this point of view makes it easy to extend their definition from grids to Cayley graphs. Cayley graphs have a number of useful features: the ability to graphically represent finitely generated group elements and their relations; to name all vertices relative to an origin; and the fact that they have a well-defined notion of translation. We propose a notion of graphs, which preserves or generalizes these features. Whereas Cayley graphs are very regular, generalized Cayley graphs are arbitrary, although of a bounded degree. We extend cellular automata theory to these arbitrary, bounded degree, time-varying graphs. The obtained notion of cellular automata is stable under composition and under inversion.
Cambridge University Press (CUP)
Title: Cellular automata over generalized Cayley graphs
Description:
It is well-known that cellular automata can be characterized as the set of translation-invariant continuous functions over a compact metric space; this point of view makes it easy to extend their definition from grids to Cayley graphs.
Cayley graphs have a number of useful features: the ability to graphically represent finitely generated group elements and their relations; to name all vertices relative to an origin; and the fact that they have a well-defined notion of translation.
We propose a notion of graphs, which preserves or generalizes these features.
Whereas Cayley graphs are very regular, generalized Cayley graphs are arbitrary, although of a bounded degree.
We extend cellular automata theory to these arbitrary, bounded degree, time-varying graphs.
The obtained notion of cellular automata is stable under composition and under inversion.
Related Results
On isomorphisms of m-Cayley digraphs
On isomorphisms of m-Cayley digraphs
The isomorphism problem for digraphs is a fundamental problem in graph theory. This problem for Cayley digraphs has been extensively investigated over the last half a century. In t...
Finite edge-transitive Cayley graphs and rotary Cayley maps
Finite edge-transitive Cayley graphs and rotary Cayley maps
This paper aims to develop a theory for studying Cayley graphs, especially for those with a high degree of symmetry. The theory consists of analysing several types of basic Cayley ...
The Cayley Isomorphism Property for Cayley Maps
The Cayley Isomorphism Property for Cayley Maps
The Cayley Isomorphism property for combinatorial objects was introduced by L. Babai in 1977. Since then it has been intensively studied for binary relational structures: graphs, d...
Power Cayley Graphs of Dihedral Groups with Certain Order
Power Cayley Graphs of Dihedral Groups with Certain Order
Combination of the concepts of power graph and Cayley graph associated to groups has led to the introduction to two new variations of Cayley graph known as the union power Cayley g...
A Unified Model for Real-Time Systems: Symbolic Techniques and Implementation
A Unified Model for Real-Time Systems: Symbolic Techniques and Implementation
AbstractIn this paper, we consider a model of generalized timed automata (GTA) with two kinds of clocks, history and future, that can express many timed features succinctly, includ...
Simulations for Event-Clock Automata
Simulations for Event-Clock Automata
Event-clock automata (ECA) are a well-known semantic subclass of timed
automata (TA) which enjoy admirable theoretical properties, e.g.,
determinizability, and are practically usef...
Permutation Groups in Automata Diagrams
Permutation Groups in Automata Diagrams
Automata act as classical models for recognition devices. From the previous researches, the classical models of automata have been used to scan strings and to determine the types o...
Roughness in Fuzzy Cayley Graphs
Roughness in Fuzzy Cayley Graphs
Rough set theory is a worth noticing approach for inexact and uncertain system modelling. When rough set theory accompanies with fuzzy set theory, which both are a complementary ge...