• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

A Note on the Proof of Cobham's Theorem

Tomi Kärki, A Note on the Proof of Cobham's Theorem. TUCS Technical Reports 713, Turku Centre for Computer Science, 2005.

Abstract:

The famous theorem of Cobham says that, for multiplicatively
independent integers k and l, any subset of natural numbers, which
is both k- and l-recognizable, is recognizable. Many of its
proofs are based on so called Hansel's lemma stating that such a
k- and l-recognizable set is syndetic. We consider these proofs
and point out that some of them are inadequate.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tKarki05a,
  title = {A Note on the Proof of Cobham's Theorem},
  author = {Kärki, Tomi},
  number = {713},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2005},
  keywords = {recognizability, Cobham's theorem, Hansel's lemma, multiplicative independence, right dense set, syndetic set},
  ISBN = {952-12-1610-7},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication