On the Periodicity of Morphic Words

Reference : On the Periodicity of Morphic Words


	Document type :	Scientific congresses and symposiums : Paper published in a journal
	Discipline(s) :	Engineering, computing & technology : Computer science Physical, chemical, mathematical & earth Sciences : Mathematics
	To cite this reference:	http://hdl.handle.net/2268/35479

Title :	On the Periodicity of Morphic Words
Language :	English
Author, co-author :	Halava, Vesa [ > > ]
	Harju, Tero [ > > ]
	Kärki, Tomi [ > > ]
	Rigo, Michel [Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes >]
Publication date :	2010
Journal title :	Lecture Notes in Computer Science
Publisher :	Springer
Volume :	6224
Pages :	209-217
Peer reviewed :	Yes
On invitation :	No
Audience :	International
ISSN :	0302-9743
e-ISSN :	1611-3349
City :	Berlin
Country :	Germany
Event name :	Developments in Language Theory
Event place (city) :	London, Ontario
Event country :	Canada
Keywords :	[en] automatic sequence ; decidability ; morphic word ; periodicity ; similarity relation
Abstract :	[en] Given a morphism h prolongable on a and an integer p, we present an algorithm that calculates which letters occur infinitely often in congruent positions modulo p in the infinite word hω(a). As a corollary, we show that it is decidable whether a morphic word is ultimately p-periodic. Moreover, using our algorithm we can find the smallest similarity relation such that the morphic word is ultimately relationally p-periodic. The problem of deciding whether an automatic sequence is ultimately weakly R-periodic is also shown to be decidable.
Target :	Researchers
Permalink :	http://hdl.handle.net/2268/35479
DOI :	10.1007/978-3-642-14455-4_20

File(s) associated to this reference

Fulltext file(s):

	File	Commentary	Version	Size	Access
Restricted access	DPer(LNCS)2.pdf		Author preprint	135.55 kB	Request copy

All documents in ORBi are protected by a user license.