|
Search: id:A131747
|
|
|
| A131747 |
|
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}^*. |
|
+0
1
|
|
| 1, 1, 1, 3, 11, 32, 152, 625, 3152, 16154, 90993, 539181, 3398803, 22561791, 157493522
(list; graph; listen)
|
|
|
OFFSET
|
1,4
|
|
|
COMMENT
|
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).
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).
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.
|
|
REFERENCES
|
D. Hamm and J. Shallit, "Characterization of finite and one-sided infinite fixed points of morphisms on free monoids". Technical Report CS-99-17, Dep. of Computer Science, University of Waterloo, 1999. http://www.cs.uwaterloo.ca/~shallit/papers.html
D. Reidenbach, "Discontinuities in pattern inference". Theoretical Computer Science. To appear.
D. Reidenbach and J. C. Schneider, "Morphically Primitive Words". In Pierre Arnoux, Nicolas Bedaride, and Julien Cassaigne, editors, Proc. 6th International Conference on Words, WORDS 2007, pages 262-272. 2007. http://www-agrw.informatik.uni-kl.de/~schneide/files/reidenbach_schneider_morphically_primitive_words.pdf
|
|
LINKS
|
D. D. Freydenberger, D. Reidenbach and J. C. Schneider, "Unambiguous Morphic Images of Strings". [Download]International Journal of Foundations of Computer Science 17, pages 601-628. 2006.
Daniel Reidenbach, Home Page
Johannes C. Schneider, Home Page
|
|
EXAMPLE
|
For length n = 3, the following words w in {1,2,3,...}^* are morphically primitive:
1 1 1 1
1 1 2 2
1 2 2 1
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).
|
|
CROSSREFS
|
Cf. A000110.
Sequence in context: A141211 A125671 A034561 this_sequence A079996 A124640 A081673
Adjacent sequences: A131744 A131745 A131746 this_sequence A131748 A131749 A131750
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Johannes C. Schneider (jschneider(AT)informatik.uni-kl.de), Oct 04 2007
|
|
|
Search completed in 0.002 seconds
|
