9 citations · 29 across the 21 of their papers we have counts for
25 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…
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…
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…
From Relation to Emulation and Interpretation: Computer Algebra Implementation of the Covering Lemma for Finite Transformation Semigroups
Attila Egri-Nagy, Chrystopher L. Nehaniv
We give a practical computer algebra implementation of the Covering Lemma for finite transformation semigroups. The lemma states that given a surjective relational morphism $(X,S)\…
Self-Reproduction and Evolution in Cellular Automata: 25 Years after Evoloops
Hiroki Sayama, Chrystopher L. Nehaniv
The year of 2024 marks the 25th anniversary of the publication of evoloops, an evolutionary variant of Chris Langton's self-reproducing loops which proved constructively that Darwi…
Hierarchical Complexity of Finite Groups
Chrystopher L. Nehaniv
What are simplest ways to construct a finite group from its atomic constituents? To understand part-whole relations between finite simple groups and the global structure of finite…
Spatial Iterated Prisoner's Dilemma as a Transformation Semigroup
Isaiah Farahbakhsh, Chrystopher L. Nehaniv
The prisoner's dilemma (PD) is a game-theoretic model studied in a wide array of fields to understand the emergence of cooperation between rational self-interested agents. In this…
Algebraic Structure of the Varikon Box
Jason d'Eon, Chrystopher L. Nehaniv
The 15-Puzzle is a well studied permutation puzzle. This paper explores the group structure of a three-dimensional variant of the 15-Puzzle known as the Varikon Box, with the goal…
Algebraic Structure and Complexity of Bootstrap Percolation with External Inputs
Saptarshi Pal, Chrystopher L. Nehaniv
In this paper a modification of the standard Bootstrap Percolation model is introduced. In our modification a discrete time update rule is constructed that allows for non-monotonic…
Exploring Tetris as a Transformation Semigroup
Peter C. Jentsch, Chrystopher L. Nehaniv
Tetris is a popular puzzle video game, invented in 1984. We formulate two versions of the game as a transformation semigroup and use this formulation to view the game through the l…
Measuring Time with Minimal Clocks
Andrei D. Robu, Christoph Salge, Chrystopher L. Nehaniv +1
Being able to measure time, whether directly or indirectly, is a significant advantage for an organism. It allows for the timely reaction to regular or predicted events, reducing t…
Robots Learning to Say `No': Prohibition and Rejective Mechanisms in Acquisition of Linguistic Negation
Frank Förster, Joe Saunders, Hagen Lehmann +1
`No' belongs to the first ten words used by children and embodies the first active form of linguistic negation. Despite its early occurrence the details of its acquisition process…
Simulating and Reconstructing Neurodynamics with Epsilon-Automata Applied to Electroencephalography (EEG) Microstate Sequences
Chrystopher L. Nehaniv, Elena Antonova
We introduce new techniques to the analysis of neural spatiotemporal dynamics via applying -machine reconstruction to electroencephalography (EEG) microstate sequences. Microsta…
Time as it could Be measured in Artificial Living Systems
Andrei D. Robu, Christoph Salge, Chrystopher L. Nehaniv +1
Being able to measure time, whether directly or indirectly, is a significant advantage for an organism. It permits it to predict regular events, and prepare for them on time. Thus,…
The maximal subgroups and the complexity of the flow semigroup of finite (di)graphs
Gábor Horváth, Chrystopher L. Nehaniv, Károly Podoski
The flow semigroup, introduced by John Rhodes, is an invariant for digraphs and a complete invariant for graphs. After collecting together previous partial results, we refine and p…
Computational Holonomy Decomposition of Transformation Semigroups
Attila Egri-Nagy, Chrystopher L. Nehaniv
We present an understandable, efficient, and streamlined proof of the Holonomy Decomposition for finite transformation semigroups and automata. This constructive proof closely foll…
SgpDec: Cascade (De)Compositions of Finite Transformation Semigroups and Permutation Groups
Attila Egri-Nagy, James D. Mitchell, Chrystopher L. Nehaniv
We describe how the SgpDec computer algebra package can be used for composing and decomposing permutation groups and transformation semigroups hierarchically by directly constructi…
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…
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…
Cascade Product of Permutation Groups
Attila Egri-Nagy, Chrystopher L. Nehaniv
Motivated by computational efficiency in algebraic automata theory here we define the cascade product of permutation groups as an external product, as a generic extension. It is th…
Interaction Histories and Short Term Memory: Enactive Development of Turn-taking Behaviors in a Childlike Humanoid Robot
Frank Broz, Chrystopher L. Nehaniv, Hatice Kose-Bagci +1
In this article, an enactive architecture is described that allows a humanoid robot to learn to compose simple actions into turn-taking behaviors while playing interaction games wi…
On Straight Words and Minimal Permutators in Finite Transformation Semigroups
Attila Egri-Nagy, Chrystopher L. Nehaniv
Motivated by issues arising in computer science, we investigate the loop-free paths from the identity transformation and corresponding straight words in the Cayley graph of a finit…
Subgroup Chains and Lagrange Coordinatizations of Finite Permutation Groups
Attila Egri-Nagy, Chrystopher L. Nehaniv
We give a general constructive proof for hierarchical coordinatizations (Lagrange Decompositions) of permutation groups. The generalization originates from the investigation of how…