2007/04/02 by Yuri Pritykin, Pritykin, Yuri
Computer Science · #Discrete Mathematics (cs.DM) #F.2.2 #F.4.3 #FOS: Computer and information sciences #G.2.1 #Logic in Computer Science (cs.LO) #cs.DM #cs.LO
paper · pdf · doi:10.48550/arxiv.0704.0218
9 pages. To be presented on 11th International Conference on Developments in Language Theory (DLT'2007), Turku, Finland, July 2007.
arxiv created 2007/04/02 · arxiv updated 2009/12/01
In some particular cases we give criteria for morphic sequences to be almost periodic (=uniformly recurrent). Namely, we deal with fixed points of non-erasing morphisms and with automatic sequences. In both cases a polynomial-time algorithm solving the problem is found. A result more or less supporting the conjecture of decidability of the general problem is given.