Quantitative estimates for the size of an intersection of sparse automatic sets

DOI10.1016/J.TCS.2023.114144arXiv2304.09223MaRDI QIDQ6077073FDOQ6077073

Authors: Seda Albayrak, Jason P. Bell 

Publication date: 17 October 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: A theorem of Cobham says that if $k$ and $ell$ are two multiplicatively independent natural numbers then a subset of the natural numbers that is both $k$- and $ell$-automatic is eventually periodic. A multidimensional extension was later given by Semenov. In this paper, we give a quantitative version of the Cobham-Semenov theorem for sparse automatic sets, showing that the intersection of a sparse $k$-automatic subset of $mathbb{N}^d$ and a sparse $ell$-automatic subset of $mathbb{N}^d$ is finite with size that can be explicitly bounded in terms of data from the automata that accept these sets.

Full work available at URL: https://arxiv.org/abs/2304.09223

zbMATH Keywords

sparse setsCobham's theoremautomatic setsindependent bases

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Automatic Sequences
• Primary cyclotomic units and a proof of Catalans conjecture
• A generalization of Cobham's theorem
• On the base-dependence of sets of numbers recognizable by finite automata
• Cobham's theorem for substitutions
• Finding the growth rate of a regular or context-free language in polynomial time
• Linear equations in variables which lie in a multiplicative group
• On the algebraicity of generalized power series
• Bounded Regular Sets
• Small points on subvarieties of a torus
• State complexity of projected languages
• A Skolem-Mahler-Lech theorem in positive characteristic and finite automata
• Unit Equations in Diophantine Number Theory
• Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems
• S-unit equations over number fields
• Function fields in positive characteristic: expansions and Cobham's theorem
• A generalization of Cobham's theorem for regular sequences
• F -structures and integral points on semiabelian varieties over finite fields
• Finite automata and algebraic extensions of functions fields
• \(F\)-sets and finite automata
• Title not available (Why is that?)
• A problem about Mahler functions
• Some Unconventional Problems in Number Theory
• Consistent systems of linear differential and difference equations
• On Cobham's theorem
• A refinement of Christol's theorem for algebraic power series
• The upper density of an automatic set is rational
• A more reasonable proof of Cobham's theorem

This page was built for publication: Quantitative estimates for the size of an intersection of sparse automatic sets

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