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

DOI10.1016/j.tcs.2023.114144arXiv2304.09223MaRDI QIDQ6077073

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)

Cites Work

• Unnamed Item
• Cobham's theorem for substitutions
• Finite automata and algebraic extensions of functions fields
• S-unit equations over number fields
• Small points on subvarieties of a torus
• A generalization of Cobham's theorem
• Linear equations in variables which lie in a multiplicative group
• Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems
• A refinement of Christol's theorem for algebraic power series
• \(F\)-sets and finite automata
• The upper density of an automatic set is rational
• On Cobham's theorem
• Consistent systems of linear differential and difference equations
• On the algebraicity of generalized power series
• A Skolem-Mahler-Lech theorem in positive characteristic and finite automata
• Function fields in positive characteristic: expansions and Cobham's theorem
• A generalization of Cobham's theorem for regular sequences
• Unit Equations in Diophantine Number Theory
• A problem about Mahler functions
• FINDING THE GROWTH RATE OF A REGULAR OR CONTEXT-FREE LANGUAGE IN POLYNOMIAL TIME
• Some Unconventional Problems in Number Theory
• Automatic Sequences
• Primary cyclotomic units and a proof of Catalans conjecture
• F -structures and integral points on semiabelian varieties over finite fields
• State Complexity of Projected Languages
• Bounded Regular Sets
• On the base-dependence of sets of numbers recognizable by finite automata
• A More Reasonable Proof of Cobham’s Theorem