Reference : On Cobham's theorem

	Document type :	Parts of books : Contribution to collective works
	Discipline(s) :	Engineering, computing & technology : Computer science Physical, chemical, mathematical & earth Sciences : Mathematics
	To cite this reference:	http://hdl.handle.net/2268/39461

Title :	On Cobham's theorem
Language :	English
Author, co-author :	Durand, Fabien [> >]
	Rigo, Michel [Université de Liège - ULg > Département de mathématique > Mathématiques discrètes >]
Publication date :	In press
Main document title :	Handbook of Automata
Alternative title :	[en] from Mathematics to Applications
Publisher :	European Math. Society Publishing house
City :	Zurich
Country :	Suisse
Keywords :	[en] Numeration systems ; Recognizable sets ; Cobham's theorem ; Ultimate periodicity ; Dynamical systems ; Substitutions
Abstract :	[en] Let k >= 2 be an integer. A set X of integers is k-recognizable if the language of k-ary representations of the elements in X is accepted by a finite automaton. The celebrated theorem of Cobham from 1969 states that if a set of integers is both k-recognizable and ℓ-recognizable, then it is a finite union of arithmetic progressions. We present several extensions of this result to nonstandard numeration systems, we describe the relationships with substitutive and automatic words and list Cobham-type results in various contexts.
Target :	Researchers ; Professionals ; Students
Permalink :	http://hdl.handle.net/2268/39461
Commentary :	2010 Mathematics Subject Classification: 68Q45, 68R15, 11B85, 11A67, 11U05, 37B20

	File(s) associated to this reference
	Fulltext file(s): File Commentary Version Size Access Open access cobham.pdf Author preprint 346.4 kB View/Open

All documents in ORBi are protected by a user license.

 

© ULg Library Network |  Feedback |  ORBi legal notices

Dspace v1.5