6 papers
Measuring the Computational Power of Finite Patches of Cellular Automata
Attila Egri-Nagy, Chrystopher L. Nehaniv
Computational power can be measured by assigning an algebraic structure to a computational device. Here, we convert a small patch of Conway's Game of Life into a transformation sem…
Skeleton Key: Subduction Classes in Finite Transformation Semigroups and Green's Relations
Attila Egri-Nagy, Chrystopher L. Nehaniv
We establish key connections between Green's - and -relations on a finite semigroup and the subduction relation defined on the image sets of an action of the same s…
Computational Exploration of Finite Semigroupoids
Attila Egri-Nagy, Chrystopher L. Nehaniv
Recent algorithmic advances in algebraic automata theory drew attention to semigroupoids (semicategories). These are mathematical descriptions of typed computational processes, but…
The Attractor-Cycle Notation for Finite Transformations
Attila Egri-Nagy, Chrystopher L. Nehaniv
We describe a new notation for finite transformations. This attractor-cycle notation extends the orbit-cycle notation for permutations and builds upon existing transformation notat…
Representation Independent Decompositions of Computation
Attila Egri-Nagy, Chrystopher L. Nehaniv
Constructing complex computation from simpler building blocks is a defining problem of computer science. In algebraic automata theory, we represent computing devices as semigroups.…
On Constructing Finite Automata by Relational Programming
Attila Egri-Nagy, Chrystopher L. Nehaniv
We consider ways to construct a transducer for a given set of input word to output symbol pairs. This is motivated by the need for representing game playing programs in a low-level…