Automata and tame expansions of (\mathbb{Z},+)

DOI10.1007/S11856-022-2322-6MaRDI QIDQ6344143arXivFDO

Authors Christopher D. C. Hawthorne

Publication date 30 June 2020

Published in arXiv

Full work available at URL https://doi.org/10.1007/S11856-022-2322-6

Mathematics Subject Classification ID

General logic (03Bxx) Model theory (03Cxx) Sequences and sets (11Bxx)

arXiv classification

math.LO

Abstract: The problem of characterizing which automatic sets of integers are stable is here solved. Given a positive integer $d$ and a subset $AsubseteqmathbbZ$ whose set of representations base $d$ is recognized by a finite automaton, a necessary condition is found for $x+yinA$ to be a stable formula in $operatornameTh(mathbbZ,+,A)$. Combined with a theorem of Moosa and Scanlon this gives a combinatorial characterization of the $d$-automatic $AsubseteqmathbbZ$ such that $(mathbbZ,+,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 $(mathbbZ,+)$, in particular the expansion by the monoid $(d^{m}athbbN,imes)$.

This page was built for publication: Automata and tame expansions of $(\mathbb{Z},+)$

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6344143)