Syndeticity and independent substitutions

Reference : Syndeticity and independent substitutions


	Document type :	Scientific journals : Article
	Discipline(s) :	Engineering, computing & technology : Computer science Physical, chemical, mathematical & earth Sciences : Mathematics
	To cite this reference:	http://hdl.handle.net/2268/15908

Title :	Syndeticity and independent substitutions
Language :	English
Author, co-author :	Durand, Fabien [ > > ]
	Rigo, Michel [Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes >]
Publication date :	2009
Journal title :	Advances in Applied Mathematics
Publisher :	Academic Press
Volume :	42
Pages :	1-22
Peer reviewed :	Yes (verified by ORBi)
Audience :	International
ISSN :	0196-8858
e-ISSN :	1090-2074
	1090-2074
Keywords :	[en] Syndeticity ; Morphism ; Cobham's theorem ; Abstract numeration system ; Regular language ; Substitution
Abstract :	[en] We associate in a canonical way a substitution to any abstract numeration system built on a regular language. In relationship with the growth order of the letters, we de ne the notion of two independent substitutions. Our main result is the following. If a sequence x is generated by two independent substitutions, at least one being of exponential growth, then the factors of x appearing in nitely often in x appear with bounded gaps. As an application, we derive an analogue of Cobham's theorem for two independent substitutions (or abstract numeration systems) one with polynomial growth, the other being exponential.
Target :	Researchers
Permalink :	http://hdl.handle.net/2268/15908
DOI :	10.1016/j.aam.2008.02.001

File(s) associated to this reference

Fulltext file(s):

	File	Commentary	Version	Size	Access
Restricted access	rd.pdf		Author preprint	202.71 kB	Request copy

All documents in ORBi are protected by a user license.