Search

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)\twoheadrightarrow(Y,T)$, we can establish emulation by a cascade product (subsemigroup of the wreath product): $(X,S)\hookrightarrow (Y,T)\wr (Z,U)$. The dependent component $(Z,U)$ contains the kernel of the morphism, the information lost in the map. The implementation complements the existing tools for the holonomy decomposition algorithm. It gives an incremental method to get a coarser decomposition when computing the complete skeleton for holonomy is not feasible. Here, we describe a simplified and generalized algorithm for the lemma and compare it to the holonomy method. Incidentally, the kernel-based method could be the easiest way of understanding the hierarchical decompositions of transformation semigroups and thus the celebrated Krohn-Rhodes theory., Comment: 13 pages, 3 figures, v2: clarifications and added example computer algebra session; final version will be published elsewhere

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 Darwinian evolution of self-reproducing organisms by variation and natural selection is possible within deterministic cellular automata. Over the last few decades, this line of Artificial Life research has since undergone several important developments. Although it experienced a relative dormancy of activities for a while, the recent rise of interest in open-ended evolution and the success of continuous cellular automata models have brought researchers' attention back to how to make spatio-temporal patterns self-reproduce and evolve within spatially distributed computational media. This article provides a review of the relevant literature on this topic over the past 25 years and highlights the major accomplishments made so far, the challenges being faced, and promising future research directions., Comment: 21 pages, 2 figures

Continual learning (CL) has emerged as an important avenue of research in recent years, at the intersection of Machine Learning (ML) and Human-Robot Interaction (HRI), to allow robots to continually learn in their environments over long-term interactions with humans. Most research in continual learning, however, has been robot-centered to develop continual learning algorithms that can quickly learn new information on static datasets. In this paper, we take a human-centered approach to continual learning, to understand how humans teach continual learning robots over the long term and if there are variations in their teaching styles. We conducted an in-person study with 40 participants that interacted with a continual learning robot in 200 sessions. In this between-participant study, we used two different CL models deployed on a Fetch mobile manipulator robot. An extensive qualitative and quantitative analysis of the data collected in the study shows that there is significant variation among the teaching styles of individual users indicating the need for personalized adaptation to their distinct teaching styles. The results also show that although there is a difference in the teaching styles between expert and non-expert users, the style does not have an effect on the performance of the continual learning robot. Finally, our analysis shows that the constrained experimental setups that have been widely used to test most continual learning techniques are not adequate, as real users interact with and teach continual learning robots in a variety of ways. Our code is available at https://github.com/aliayub7/cl_hri., Comment: Accepted to the IEEE International Conference on Robot and Human Interactive Communication (ROMAN), 2023

For robots to assist users with household tasks, they must first learn about the tasks from the users. Further, performing the same task every day, in the same way, can become boring for the robot's user(s), therefore, assistive robots must find creative ways to perform tasks in the household. In this paper, we present a cognitive architecture for a household assistive robot that can learn personalized breakfast options from its users and then use the learned knowledge to set up a table for breakfast. The architecture can also use the learned knowledge to create new breakfast options over a longer period of time. The proposed cognitive architecture combines state-of-the-art perceptual learning algorithms, computational implementation of cognitive models of memory encoding and learning, a task planner for picking and placing objects in the household, a graphical user interface (GUI) to interact with the user and a novel approach for creating new breakfast options using the learned knowledge. The architecture is integrated with the Fetch mobile manipulator robot and validated, as a proof-of-concept system evaluation in a large indoor environment with multiple kitchen objects. Experimental results demonstrate the effectiveness of our architecture to learn personalized breakfast options from the user and generate new breakfast options never learned by the robot., Comment: Accepted at IEEE International Conference on Robot and Human Interactive Communication (ROMAN), 2023

For long-term deployment in dynamic real-world environments, assistive robots must continue to learn and adapt to their environments. Researchers have developed various computational models for continual learning (CL) that can allow robots to continually learn from limited training data, and avoid forgetting previous knowledge. While these CL models can mitigate forgetting on static, systematically collected datasets, it is unclear how human users might perceive a robot that continually learns over multiple interactions with them. In this paper, we developed a system that integrates CL models for object recognition with a Fetch mobile manipulator robot and allows human participants to directly teach and test the robot over multiple sessions. We conducted an in-person study with 60 participants who interacted with our system in 300 sessions (5 sessions per participant). We conducted a between-participant study with three different CL models (3 experimental conditions) to understand human perceptions of continual learning robots over multiple sessions. Our results suggest that participants' perceptions of trust, competence, and usability of a continual learning robot significantly decrease over multiple sessions if the robot forgets previously learned objects. However, the perceived task load on participants for teaching and testing the robot remains the same over multiple sessions even if the robot forgets previously learned objects. Our results also indicate that state-of-the-art CL models might perform unreliably when applied to robots interacting with human participants. Further, continual learning robots are not perceived as very trustworthy or competent by human participants, regardless of the underlying continual learning model or the session number., Comment: 36 pages, 8 figures. Under review

Assistive robots operating in household environments would require items to be available in the house to perform assistive tasks. However, when these items run out, the assistive robot must remind its user to buy the missing items. In this paper, we present a computational architecture that can allow a robot to learn personalized contextual knowledge of a household through interactions with its user. The architecture can then use the learned knowledge to make predictions about missing items from the household over a long period of time. The architecture integrates state-of-the-art perceptual learning algorithms, cognitive models of memory encoding and learning, a reasoning module for predicting missing items from the household, and a graphical user interface (GUI) to interact with the user. The architecture is integrated with the Fetch mobile manipulator robot and validated in a large indoor environment with multiple contexts and objects. Our experimental results show that the robot can adapt to an environment by learning contextual knowledge through interactions with its user. The robot can also use the learned knowledge to correctly predict missing items over multiple weeks and it is robust against sensory and perceptual errors., Comment: Accepted at IEEE ICDL 2022

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 groups, we axiomatize complexity measures on finite groups. From the Jordan-H\"older theorem and Frobenius-Lagrange embedding in an iterated wreath product, any finite group $G$ can be constructed from a unique collection of simple groups, its Jordan-H\"older factors, each with well-defined multiplicities through iterated extension. What is the least number of levels needed in such a hierarchical construction if a level is allowed to include several of these atomic pieces? To answer this question rigorously, we give a natural set of hierarchical complexity axioms for finite groups, and prove these axioms are satisfied by a unique maximal complexity function $\mathbf{cx}$. We prove this function is the same as the minimal number of "spans of gems" (direct products of simple groups) in a subnormal series with all factors of this type. This hierarchical complexity is thus effectively computable, and bounded below by all other complexity measures satisfying the axioms, including generalizations of derived length and Fitting height. For solvable groups, the unique maximal group complexity measure satisfying the axioms agrees with the restriction of the one for all finite groups, and in addition satisfies an embedding axiom. In both cases, the complexity of a group is bounded above and below by various natural functions. In particular, hierarchical complexity is sharply bounded above by socle length, with a canonical decomposition. Examples illustrate applications of the bounds and axiomatic methods in determining complexity of groups. We show also that minimal decompositions need not be unique in terms of what components occur nor their ordering. The complexity axioms are also shown to be independent.

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 work, we formulate a spatial iterated PD as a discrete-event dynamical system where agents play the game in each time-step and analyse it algebraically using Krohn-Rhodes algebraic automata theory using a computational implementation of the holonomy decomposition of transformation semigroups. In each iteration all players adopt the most profitable strategy in their immediate neighbourhood. Perturbations resetting the strategy of a given player provide additional generating events for the dynamics. Our initial study shows that the algebraic structure, including how natural subsystems comprising permutation groups acting on the spatial distributions of strategies, arise in certain parameter regimes for the pay-off matrix, and are absent for other parameter regimes. Differences in the number of group levels in the holonomy decomposition (an upper bound for Krohn-Rhodes complexity) are revealed as more pools of reversibility appear when the temptation to defect is at an intermediate level. Algebraic structure uncovered by this analysis can be interpreted to shed light on the dynamics of the spatial iterated PD., Comment: 10 pages, 10 figures, for code used in this paper see https://git.io/JJJcN

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 of providing a heuristic that would help a human solve it while minimizing the number of moves. First, we show by a parity argument which configurations of the puzzle are reachable. We define a generating set based on the three dimensions of movement, which generates a group that acts on the puzzle configurations, and we explore the structure of this group. Finally, we show a heuristic for solving the puzzle by writing an element of the symmetry group as a word in terms of a generating set, and we compute the shortest possible word for each puzzle configuration., Comment: 9 pages, 10 figures

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-monotonicity - unlike its classical counterpart. External inputs to drive the system into desirable states are also included in the model. The algebraic structure and complexity properties of the system are inferred by studying the system's holonomy decomposition. We introduce methods of inferring the pools of reversibility for the system. Dependence of system complexity on process parameters is presented and discussed., Comment: 10 pages, 5 Figures, Accepted with Minor Changes at Recent Advances in Mathematical and Statistical Methods, Proceedings of AMMCS - 2019

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 lens of Krohn-Rhodes theory. In a variation of the game upon which it restarts if the player loses, we find permutation group structures, including the symmetric group $S_5$ which contains a non-abelian simple group as a subgroup. This implies, at least in a simple case, that iterated Tetris is finitarily computationally universal.

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 the pressure for fast processing of sensory input. Thus, clocks are ubiquitous in biology. In the present paper, we consider minimal abstract pure clocks in different configurations and investigate their characteristic dynamics. We are especially interested in optimally time-resolving clocks. Among these, we find fundamentally diametral clock characteristics, such as oscillatory behavior for purely local time measurement or decay-based clocks measuring time periods of a scale global to the problem. We include also sets of independent clocks ("clock bags"), sequential cascades of clocks and composite clocks with controlled dependency. Clock cascades show a "condensation effect" and the composite clock shows various regimes of markedly different dynamics., Comment: Article submitted to the Artificial Life journal selected papers from ECAL 2017 issue. This document is the version after the review phase. Journal version of arXiv:1706.07091

`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 remain largely unknown. The circumstance that `no' cannot be construed as a label for perceptible objects or events puts it outside of the scope of most modern accounts of language acquisition. Moreover, most symbol grounding architectures will struggle to ground the word due to its non-referential character. In an experimental study involving the child-like humanoid robot iCub that was designed to illuminate the acquisition process of negation words, the robot is deployed in several rounds of speech-wise unconstrained interaction with na\"ive participants acting as its language teachers. The results corroborate the hypothesis that affect or volition plays a pivotal role in the socially distributed acquisition process. Negation words are prosodically salient within prohibitive utterances and negative intent interpretations such that they can be easily isolated from the teacher's speech signal. These words subsequently may be grounded in negative affective states. However, observations of the nature of prohibitive acts and the temporal relationships between its linguistic and extra-linguistic components raise serious questions over the suitability of Hebbian-type algorithms for language grounding., Comment: Submitted journal article. 21 pages main paper plus 28 pages supplementary information / appendix. 8 figures in main paper

We introduce new techniques to the analysis of neural spatiotemporal dynamics via applying $\epsilon$-machine reconstruction to electroencephalography (EEG) microstate sequences. Microstates are short duration quasi-stable states of the dynamically changing electrical field topographies recorded via an array of electrodes from the human scalp, and cluster into four canonical classes. The sequence of microstates observed under particular conditions can be considered an information source with unknown underlying structure. $\epsilon$-machines are discrete dynamical system automata with state-dependent probabilities on different future observations (in this case the next measured EEG microstate). They artificially reproduce underlying structure in an optimally predictive manner as generative models exhibiting dynamics emulating the behaviour of the source. Here we present experiments using both simulations and empirical data supporting the value of associating these discrete dynamical systems with mental states (e.g. mind-wandering, focused attention, etc.) and with clinical populations. The neurodynamics of mental states and clinical populations can then be further characterized by properties of these dynamical systems, including: i) statistical complexity (determined by the number of states of the corresponding $\epsilon$-automaton); ii) entropy rate; iii) characteristic sequence patterning (syntax, probabilistic grammars); iv) duration, persistence and stability of dynamical patterns; and v) algebraic measures such as Krohn-Rhodes complexity or holonomy length of the decompositions of these. The potential applications include the characterization of mental states in neurodynamic terms for mental health diagnostics, well-being interventions, human-machine interface, and others on both subject-specific and group/population-level.

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, clocks are ubiquitous in biology. In the present paper, we consider the most minimal abstract pure clocks and investigate their characteristics with respect to their ability to measure time. Amongst other, we find fundamentally diametral clock characteristics, such as oscillatory behaviour for local time measurement or decay-based clocks measuring time periods in scales global to the problem. We include also cascades of independent clocks ("clock bags") and composite clocks with controlled dependency; the latter show various regimes of markedly different dynamics., Comment: Accepted at the European Conference on Artificial Life 2017, Lyon, France

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 prove Rhodes's conjecture on the structure of the maximal groups in the flow semigroup for finite, antisymmetric, strongly connected digraphs. Building on this result, we investigate and fully describe the structure and actions of the maximal subgroups of the flow semigroup acting on all but $k$ points for all finite digraphs and graphs for all $k\geq 1$. A linear algorithm (in the number of edges) is presented to determine these so-called `defect $k$ groups' for any finite (di)graph. Finally, we prove that the complexity of the flow semigroup of a 2-vertex connected (and strongly connected di)graph with $n$ vertices is $n-2$, completely confirming Rhodes's conjecture for such (di)graphs., Comment: 25 pages

We present an understandable, efficient, and streamlined proof of the Holonomy Decomposition for finite transformation semigroups and automata. This constructive proof closely follows the existing computational implementation. Its novelty lies in the strict separation of several different ideas appearing in the holonomy method. The steps of the proof and the constructions are illustrated with computed examples., Comment: 16 pages, 4 figures, final version will be published elsewhere

We describe how the SgpDec computer algebra package can be used for composing and decomposing permutation groups and transformation semigroups hierarchically by directly constructing substructures of wreath products, the so called cascade products., Comment: 7 pages, 4 figures, presented at the 4th International Congress on Mathematical Software, http://sgpdec.sf.net

We establish the connection between Green's ${\mathcal J}$-classes and the subduction equivalence classes defined on the image sets of an action of a semigroup. The construction of the skeleton order (on subduction equivalence classes) is shown to depend in a functorial way on transformation semigroups and surjective morphisms, and to factor through the $\leq_{\mathcal L}$-order and $\leq_{\mathcal J}$-order on the semigroup and through the inclusion order on image sets. For right regular representations, the correspondence between the ${\mathcal J}$-class order and the skeleton is one of isomorphism., Comment: 8 pages

We describe a new notation for finite transformations. This attractor-cycle notation extends the orbit-cycle notation for permutations and builds upon existing transformation notations. How the basins of attraction of a finite transformation flow into permuted orbit cycles is visible from the notation. It gives insight into the structure of transformations and reduces the length of expressions without increasing the number of types of symbols., Comment: 8 pages, 4 figures, notation itself and the title changed!, this final version is implemented in SgpDec http://gap-packages.github.io/sgpdec/

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 the most general hierarchical product that uses arbitrary total functions to combine a linearly ordered set of permutation groups. Algebraically speaking, cascade products are explicitly constructed substructures of the iterated wreath product. We show how direct, semidirect and wreath products can be described as cascade products and we also discuss examples of composite groups that can only be constructed exactly as generic extensions by cascade products. The cascade construction naturally generalizes to the transformation semigroup case by leaving out the details of defining inverse operations., Comment: 12 pages, 4 figures, v5: updated link to software package and minor changes

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 with a human partner. The robot's action choices are reinforced by social feedback from the human in the form of visual attention and measures of behavioral synchronization. We demonstrate that the system can acquire and switch between behaviors learned through interaction based on social feedback from the human partner. The role of reinforcement based on a short term memory of the interaction is experimentally investigated. Results indicate that feedback based only on the immediate state is insufficient to learn certain turn-taking behaviors. Therefore some history of the interaction must be considered in the acquisition of turn-taking, which can be efficiently handled through the use of short term memory.

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 finite transformation semigroup with a fixed generator set. Of special interest are words that permute a given subset of the state set. Certain such words, called minimal permutators, are shown to comprise a code, and the straight ones comprise a finite code. Thus, words that permute a given subset are uniquely factorizable as products of the subset's minimal permutators, and these can be further reduced to straight minimal permutators. This leads to insight into structure of local pools of reversibility in transformation semigroups in terms of the set of words permuting a given subset. These findings can be exploited in practical calculations for hierarchical decompositions of finite automata. As an example we consider groups arising in biological systems., Comment: 12 pages, 2 figures

We give a general constructive proof for hierarchical coordinatizations (Lagrange Decompositions) of permutation groups. The generalization originates from the investigation of how the subgroup chains of finite permutation groups yield different coordinate systems. The study is motivated by the practical needs and the verification of an existing computational implementation. Large scale machine calculated examples are also presented., Comment: 10 pages, 1 figure

For natural and artificial systems with some symmetry structure, computational understanding and manipulation can be achieved without learning by exploiting the algebraic structure. Here we describe this algebraic coordinatization method and apply it to permutation puzzles. Coordinatization yields a structural understanding, not just solutions for the puzzles., Comment: 14 pages, 5 figures, v2 major revision of computational examples