Reference : On the Periodicity of Morphic Words
Scientific congresses and symposiums : Paper published in a journal
Engineering, computing & technology : Computer science
Physical, chemical, mathematical & earth Sciences : Mathematics
http://hdl.handle.net/2268/35479
On the Periodicity of Morphic Words
English
Halava, Vesa [ > > ]
Harju, Tero [ > > ]
Kärki, Tomi [ > > ]
Rigo, Michel mailto [Université de Liège - ULg > Département de mathématique > Mathématiques discrètes >]
2010
Lecture Notes in Computer Science
Springer
6224
209-217
Yes
No
International
0302-9743
1611-3349
Berlin
Germany
Developments in Language Theory
London, Ontario
Canada
[en] automatic sequence ; decidability ; morphic word ; periodicity ; similarity relation
[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.
Researchers
http://hdl.handle.net/2268/35479

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Restricted access
DPer(LNCS)2.pdfAuthor preprint135.55 kBRequest copy

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.