4 papers · 1 filter
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.…
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)\…
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…
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…