/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/modulepublicimportMathlib.Data.Set.Finite.Basic@[expose]publicsection
Automatic sequences
A sequence a : ℕ → α is k-automatic if it is the output of a deterministic finite
automaton fed the base-k digits of the index. By the kernel criterion of [Eil74] this holds
exactly when the k-kernel of a is finite, and that is the definition used here: it needs no
automaton, and finiteness of the kernel is what proofs about automatic sequences consume.
For k ≥ 2, IsAutomatic k a already forces the range of a to be finite, by
AutomaticSequence.IsAutomatic.finite_range. For k ≤ 1 the k-kernel of a is {a}, so
every sequence is k-automatic.
References:
[AS03] Allouche, Jean-Paul, and Jeffrey Shallit. "Automatic Sequences: Theory,
Applications, Generalizations." Cambridge University Press, 2003.
A sequence a is k-automatic if its k-kernel is finite. By [Eil74] this is equivalent to
a being generated by a deterministic finite automaton reading the base-k digits of the
index.