A131747 - OEIS

%I #36 Aug 06 2024 05:33:00

%S 1,1,1,3,11,32,152,625,3152,16154,90993,539181,3398803,22561791,

%T 157493522,1151863409,8803760900,70149141443,581461668973,

%U 5004153572628

%N Number of morphically primitive words w in {1,2,3,...}^* of length n (modulo renaming), also the number of words (length n) which are fixed points of nontrivial morphisms, also the number of succinct patterns of length n in canonical form, also the number of words which have an unambiguous morphic image in {a,b}^*.

%C A word v is called morphically primitive iff there is no shorter word v' such that there exist a morphism mapping v onto v' and a morphism mapping v' onto v (the morphisms may erase symbols).

%C So far, no formula is known to calculate this number for any given n. Note that the number of all words w in {1,2,3,...}^* of length n modulo renaming corresponds to the Bell number of n (see A000110).

%C It would be interesting to know the limit of the ratio of morphically primitive words and all words (modulo renaming). For n = 15, this ratio is approx. 0.1139. Moreover, note that the terms "primitive (or aperiodic) words" and "morphically primitive words" are incomparable.

%H D. D. Freydenberger, D. Reidenbach and J. C. Schneider, <a href="http://dx.doi.org/10.1007/11505877_22">Unambiguous Morphic Images of Strings</a>. International Journal of Foundations of Computer Science 17 (2006), pp. 601-628.

%H D. Hamm and J. Shallit, <a href="http://www.cs.uwaterloo.ca/~shallit/Papers/hamm2.ps">Characterization of finite and one-sided infinite fixed points of morphisms on free monoids</a>. Technical Report CS-99-17, Dep. of Computer Science, University of Waterloo, 1999.

%H D. Reidenbach, <a href="https://dspace.lboro.ac.uk/dspace-jspui/bitstream/2134/3469/3/Reidenbach_TCS_Discontinuities_Pattern_Inference.pdf">Discontinuities in pattern inference</a>. Theoretical Computer Science 397(1-3) (2008), pp. 166-193. doi:10.1016/j.tcs.2008.02.029

%H D. Reidenbach and J. C. Schneider, <a href="https://citeseerx.ist.psu.edu/pdf/c9383d0aa3125689b43227dd0cb8e3ebaee10891">Morphically Primitive Words</a>. In Pierre Arnoux, Nicolas Bedaride and Julien Cassaigne, editors, Proc. 6th International Conference on Words, WORDS 2007, pages 262-272. 2007. [Different from the paper with the same name, referenced below.]

%H Daniel Reidenbach and Johannes C. Schneider, <a href="https://doi.org/10.1016/j.tcs.2009.01.020">Morphically primitive words</a>, Theoretical Computer Science, 410 (2009), 2148-2161. (<a href="https://repository.lboro.ac.uk/articles/journal_contribution/9402479">alternative link</a>) See Table 1.

%H Daniel Reidenbach, <a href="http://www-staff.lboro.ac.uk/~codr2/">Home Page</a> [dead link]

%H Johannes C. Schneider, <a href="http://www-agrw.informatik.uni-kl.de/~schneide/">Home Page</a> [dead link]

%e For length n = 4, the following words w in {1,2,3,...}^* are morphically primitive:

%e   1 1 1 1

%e   1 1 2 2

%e   1 2 2 1

%e All other words of length 4 are either renamings of those words (e.g. 3 4 4 3 is a renaming of 1 2 2 1) or morphically imprimitive (e.g. 1 2 2 2).

%Y Cf. A000110.

%K nonn,more

%O 1,4

%A Johannes C. Schneider (jschneider(AT)informatik.uni-kl.de), Oct 04 2007

%E a(16)-a(19) from _Gary Bennett_, Apr 06 2015

%E a(20) from _Gary Bennett_, Aug 25 2015