2020/06/30 by Christopher Hawthorne, Hawthorne, Christopher D. C. · 1 citation
Computer Science · #semigroups and automata theory #Cellular Automata and Applications #Computability, Logic, AI Algorithms
paper · pdf · doi:10.48550/arxiv.2007.00070
The problem of characterizing which automatic sets of integers are stable is here solved. Given a positive integer d and a subset A⊆ ℤ whose set of representations base d is recognized by a finite automaton, a necessary condition is found for x+y∈ A to be a stable formula in Th(ℤ,+,A). Combined with a theorem of Moosa and Scanlon this gives a combinatorial characterization of the d-automatic A⊆ ℤ such that (ℤ,+,A) is stable. This characterization is in terms of what were called "F-sets" by Moosa and Scanlon and "elementary p-nested sets" by Derksen. Automata-theoretic methods are also used to produce some NIP expansions of (ℤ,+), in particular the expansion by the monoid (d^ℕ,× ).