Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2508.04851 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918498752528384 |
|---|---|
| author | Bell, Jason Gorman, Alexi Block Schulz, Chris |
| author_facet | Bell, Jason Gorman, Alexi Block Schulz, Chris |
| contents | Let $k\ge 2$ and let $X$ be a subset of the natural numbers that is $k$-automatic and not eventually periodic. We show that the following dichotomy holds: either all $k$-automatic subsets are definable in the expansion of Presburger arithmetic in which we adjoin the predicate $X$, or $(\mathbb{N},+,X)$ has the same definable sets as $(\mathbb{N},+,k^{\mathbb{N}})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_04851 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Dichotomy for $k$-automatic expansions of Presburger Arithmetic Bell, Jason Gorman, Alexi Block Schulz, Chris Logic Formal Languages and Automata Theory 03C64, 03D05, 28A80 Let $k\ge 2$ and let $X$ be a subset of the natural numbers that is $k$-automatic and not eventually periodic. We show that the following dichotomy holds: either all $k$-automatic subsets are definable in the expansion of Presburger arithmetic in which we adjoin the predicate $X$, or $(\mathbb{N},+,X)$ has the same definable sets as $(\mathbb{N},+,k^{\mathbb{N}})$. |
| title | A Dichotomy for $k$-automatic expansions of Presburger Arithmetic |
| topic | Logic Formal Languages and Automata Theory 03C64, 03D05, 28A80 |
| url | https://arxiv.org/abs/2508.04851 |