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

DOI10.1016/J.TCS.2023.114144MaRDI QIDQ6077073zbMATH OpenFDO

Authors Seda Albayrak, Jason P. Bell

Publication date 17 October 2023

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

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)

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.

Cites work

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

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)