Contributions to the theory of F-automatic sets

2020/11/24 by Christopher Hawthorne, Hawthorne, Christopher
Computer Science · Mathematics · #03C45 (Primary) 11B85 #68Q45 (Secondary) #Advanced Topology and Set Theory #Computability, Logic, AI Algorithms #F.4.1 #F.4.3 #FOS: Mathematics #Logic (math.LO) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2011.12405

openalex publication_date 2020/11/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Fix an abelian group Γ and an injective endomorphism F \colon Γ→ Γ. Improving on the results of Bell and Moosa, new characterizations are here obtained for the existence of spanning sets, F-automaticity, and F-sparsity. The model theoretic status of these sets is also investigated, culminating with a combinatorial description of the F-sparse sets that are stable in (Γ, +), and a proof that the expansion of (Γ, +) by any F-sparse set is NIP. These methods are also used to show for prime p≥ 7 that the expansion of (\mathbbF_p[t], +) by multiplication restricted to t^ℕ is NIP.

Citations

• Automata and tame expansions of (ℤ,+)

Related

• F-sets and finite automata
• Stabilizers and NIP arithmetic regularity
• A decidable expansion of (Γ,+,F) with the independence property
• Some applications of the minimal model program in arithmetic dynamics
• Quantifying Brinkmann's problem: relative φ-order and φ-spectrum