A Case Study in Meta-AUTOMATION: AUTOMATIC Generation of Congruence AUTOMATA For Combinatorial Sequences

The Frobenius number $g(S)$ of a set $S$ of non-negative integers with $\gcd 1$ is the largest integer not expressible as a linear combination of elements of $S$. Given a sequence ${\bf s} = (s_i)_{i \geq 0}$, we can define the associated sequence $G_{\bf s} (i) = g(\{ s_i,s_{i+1},\ldots \})$. In this paper we compute $G_{\bf s} (i)$ for some classical automatic sequences: the evil numbers, the odious numbers, and the lower and upper Wythoff sequences. In contrast with the us...

In this paper, we give an introduction to basic concepts of automaton semigroups. While we must note that this paper does not contain new results, it is focused on extended introduction in the subject and detailed examples.

This text is an extended version of the chapter 'Automata and rational expressions' in the AutoMathA Handbook that will appear soon, published by the European Science Foundation and edited by JeanEricPin.

This paper provides a description of the algorithms employed by the Warwick AUTOMATA package for calculating the finite state automata associated with a short-lex automatic group. The aim is to provide an overview of the whole process, rather than concentrating on technical details, which have been already been published elsewhere. A number of related programs are also described.

In this paper we present a method to pass from a recurrence relation having constant coefficients (in short, a C-recurrence) to a finite succession rule defining the same number sequence. We recall that succession rules are a recently studied tool for the enumeration of combinatorial objects related to the ECO method. We also discuss the applicability of our method as a test for the positivity of a number sequence.

This is Chapter 24 in the "AutoMathA" handbook. Finite automata have been used effectively in recent years to define infinite groups. The two main lines of research have as their most representative objects the class of automatic groups (including word-hyperbolic groups as a particular case) and automata groups (singled out among the more general self-similar groups). The first approach implements in the language of automata some tight constraints on the geometry of the gro...

We generalize several recognizability theorems for free single-sorted algebras to the field of many-sorted algebras and provide, in a uniform way and without using neither regular tree grammars nor tree automata, purely algebraic proofs of them based on the concept of congruence.

In this paper we present an algorithm for computing a congruence on an inverse semigroup from a collection of generating pairs. This algorithm uses a myriad of techniques from computational group theory, automata, and the theory of inverse semigroups. An initial implementation of this algorithm outperforms existing implementations by several orders of magnitude.

This contains Part I of the book: Congruence lattices of finite lattices, which covers about 80 years of research and more than 250 papers.

We show that various aspects of k-automatic sequences -- such as having an unbordered factor of length n -- are both decidable and effectively enumerable. As a consequence it follows that many related sequences are either k-automatic or k-regular. These include many sequences previously studied in the literature, such as the recurrence function, the appearance function, and the repetitivity index. We also give some new characterizations of the class of k-regular sequences. Ma...