Kautomatic

Kautomatic refers to the concept of k-automatic sequences in automata theory and combinatorics on words. A k-automatic sequence is a sequence over a finite alphabet that can be generated by a finite automaton reading the base-k representation of the index n. In other words, there exists a deterministic finite automaton with output (DFAO) that, given the digits of n in base k, outputs the nth term of the sequence. The base-k representation is typically read in a fixed convention, often most-significant-digit first, with appropriate handling of leading zeros.

An equivalent and common characterization uses the k-kernel: the set of subsequences obtained by taking a_n for indices of the form a k^e n + r, for all e ≥ 0 and 0 ≤ r < k. A sequence is k-automatic if and only if its k-kernel is finite. This provides a practical criterion for proving automaticity and for understanding the structure of the sequence without constructing the automaton explicitly.

Prominent examples include the Thue-Morse sequence, which is 2-automatic and can be defined as the parity of the number of 1s in the binary expansion of n. More generally, many digit-based constructions in base k yield k-automatic sequences. They frequently arise in number theory and combinatorics on words, where they help study regularity, pattern occurrence, and complexity.

History and references: the theory was developed in the 1980s and 1990s by Allouche and Shallit, culminating in the monograph Automatic Sequences: Theory, Applications, Generalizations (1992). The framework has since influenced related topics such as k-regular sequences and morphic words.