New methods for WordMorphism

[staroste]

Add the following methods to the WordMorphism class:

• is_injective() - injectivity test
• is_unboundedly_repetitive() - whether the morphism is unboundedly repetitive, i.e. has a periodic point containing an unbounded letter, that is also a periodic word
• is_pushy() - whether the morphism is pushy (its language contains an infinite amount of words with no growing letters)
• is_repetitive() - whether the morphism (its language) contains arbitrarily large repetitions
• infinite_repetitions_primitive_roots() - finds the set of all words which are primitive roots of arbitrarily large repetitions in the language of the morphism
• simplify_alphabet_size() - returns a simplification of the morphism
• simplify_until_injective() - repeateadly calls simplify_alphabet_size() until the result is injective

Also adds the following method to the FiniteWord_class:

• minimal_conjugate() - returns the lexicographically smallest conjugate of this word

CC: @seblabbe @videlec @sagetrac-tmonteil @staroste

Component: combinatorics

Keywords: sd66

Author: Martin Rejmon

Branch/Commit: 0d5f94a

Reviewer: Sébastien Labbé

Issue created by migration from https://trac.sagemath.org/ticket/18119

[mrejmon]

Branch: u/gh-mrejmon/18119

[mrejmon]

comment:4

Hello,

the pushed branch contains an implementation of the algorithm from the following paper An algorithm for enumerating all infinite repetitions in a D0L-system, using which it is easy to answer the is_pushy and is_unboundedly_repetitive queries. It also includes a version of the Sardinas-Patterson algorithm to answer is_injective.

While implementing the above I also added a method for simplifying non-injective morphisms and a method for finding the minimal conjugate of a finite word.

---

New commits:

9d5b3c0

Add algorithm enumerating infinite repetitions

[mrejmon]

Commit: 9d5b3c0

[mrejmon]

Changed author from Štěpán Starosta to Martin Rejmon

[seblabbe]

comment:5

I looked at the code. Here are few comments:

1 - I would suggest to move the import of chain, count and Counter directly inside the method where they are used (except if they are imported in lots of distinct methods).

-from itertools import chain
+from collections import Counter
+from itertools import chain, count

2 - I think we want to create a class for a morphic word (see ticket #31378 on which we are currently working on with Jana) or for the language of a morphic word. And then many of the methods implemented here would go in that class. Or maybe you really want to consider \{m^n(w) | n \ge 0\} which may contain more factors than the morphic word if w is the whole alphabet and m is not primitive. Does such language corresponds to something, for which we could create a class as well?

Every method saying "should be an endomorphism" and taking w as input would go in a class representing this object. If this object is always a morphic word OR morphic language, then, we could create a class for that. If this object is more general, we could still create a class for that.

What is the typical case you have in mind?

+        Return whether the language `\{m^n(w) | n \ge 0\}` is pushy,
+        where `m` is this morphism and `w` is a word inputted as a parameter.
+
+        Requires this morphism to be an endomorphism.

[staroste]

comment:6

Replying to @seblabbe:

2 - I think we want to create a class for a morphic word (see ticket #31378 on which we are currently working on with Jana) or for the language of a morphic word. And then many of the methods implemented here would go in that class. Or maybe you really want to consider \{m^n(w) | n \ge 0\} which may contain more factors than the morphic word if w is the whole alphabet and m is not primitive. Does such language corresponds to something, for which we could create a class as well?

\{m^n(w) | n \ge 0\} is the language of an L-system, w is its axiom. I am not sure if we want to create a class for this, we rather want to study its factor closure, i.e., language of an infinite word generated by the morphism of w being a letter.
As you say, if w is not just a letter, we get something more, but in general we should no get anything really new than what we'd get by taking letter axioms one by one. Or is there, Martin?

Every method saying "should be an endomorphism" and taking w as input would go in a class representing this object. If this object is always a morphic word OR morphic language, then, we could create a class for that. If this object is more general, we could still create a class for that.

I am unsure what would be the right object at this point. In the more general settings, all are properties of a D0L-system. Do we want to have a class for it?

I think there are many general methods that require an endomorphism, and there is no special class for them, is there?

What is the typical case you have in mind?

+        Return whether the language `\{m^n(w) | n \ge 0\}` is pushy,
+        where `m` is this morphism and `w` is a word inputted as a parameter.
+
+        Requires this morphism to be an endomorphism.

I think there should be the factorial closure of \{m^n(w) | n \ge 0\} as is in the original definition Repetition of subwords in DOL languages.
Taking w a letter, it is a property of a morphic word, or more precisely, its language.
What do you mean by typical usage? Knowing whether a system/morphism is pushy is an ingredient to decide whether it is circular.

[seblabbe]

Changed commit from 9d5b3c0 to 6dcef98

[seblabbe]

comment:7

I did a small commit to move the itertools import inside the method.

(I did not touch the import of chain which would create a conflict with #31378)

---

New commits:

6dcef98

18119: moved itertools imports inside methods

[seblabbe]

Changed branch from u/gh-mrejmon/18119 to u/slabbe/18119

[mrejmon]

comment:8

Replying to @staroste:

Replying to @seblabbe:

2 - I think we want to create a class for a morphic word (see ticket #31378 on which we are currently working on with Jana) or for the language of a morphic word. And then many of the methods implemented here would go in that class. Or maybe you really want to consider \{m^n(w) | n \ge 0\} which may contain more factors than the morphic word if w is the whole alphabet and m is not primitive. Does such language corresponds to something, for which we could create a class as well?

\{m^n(w) | n \ge 0\} is the language of an L-system, w is its axiom. I am not sure if we want to create a class for this, we rather want to study its factor closure, i.e., language of an infinite word generated by the morphism of w being a letter.
As you say, if w is not just a letter, we get something more, but in general we should no get anything really new than what we'd get by taking letter axioms one by one. Or is there, Martin?

No, for these methods there isn't. I mostly only added the w argument since it seemed to make the docs cleaner to me, that is "w is a word inputted as a parameter" instead of "w is an arbitrary word containing at least one of each letter from the alphabet of the domain of this morphism" or similar.

...

...

...

+        Return whether the language `\{m^n(w) | n \ge 0\}` is pushy,
+        where `m` is this morphism and `w` is a word inputted as a parameter.
+
+        Requires this morphism to be an endomorphism.

I think there should be the factorial closure of \{m^n(w) | n \ge 0\} as is in the original definition Repetition of subwords in DOL languages.

The factors are mentioned in the paragraph right below that:

        A language created by iterating a morphism is pushy if its words
        contain an infinite number of factors containing no growing letters. It
        turns out that this is equivalent to having at least one infinite
        repetition containing no growing letters.

Would you still prefer to mention them also in the first sentence in the docs?

Replying to @seblabbe:

I did a small commit to move the itertools import inside the method.

(I did not touch the import of chain which would create a conflict with #31378)

Thanks! Sorry for the long delay before answering, thankfully Štěpán already responded to your second comment. I also added a commit adding a test and slightly refactoring one method.

---

New commits:

ba0845d

18119: Refactor inf_reps_bounded

[mrejmon]

Changed branch from u/slabbe/18119 to u/gh-mrejmon/18119

[mrejmon]

Changed commit from 6dcef98 to ba0845d

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

49e0baa	18119: Refactor inf_reps_bounded (2)
0e6e552	18119: Refactor inf_reps_growing

[sagetrac-git]

Changed commit from ba0845d to 0e6e552

[sagetrac-git]

Changed commit from 0e6e552 to 7a230ac

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

ab5c0c9	18119: Refactor is_injective
7a230ac	18119: Refactor simplify

[sagetrac-git]

Changed commit from 7a230ac to e472040

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

e472040

18119: Refactor is_injective (2)

[seblabbe]

comment:12

Replying to @seblabbe:

2 - I think we want to create a class for a morphic word (see ticket #31378 on which we are currently working on with Jana) or for the language of a morphic word. And then many of the methods implemented here would go in that class.

I just wanted to reply to myself here. While I still think some of the methods added here could go in another class (LanguageMorphicWord for instance), I do not want to uphold this ticket. I am not contributing at a high frequency right now, so I prefer adding those methods in SageMath as proposed and, later, if we want to move them elsewhere, it is never too late. Continue your good work.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

9c216e0

18119: Work around some codomain issues

[sagetrac-git]

Changed commit from e472040 to 9c216e0

[seblabbe]

comment:15

I see that few more methods are added in this ticket:

+    def is_injective(self):
+    def is_pushy(self, w=None):
+    def is_unboundedly_repetitive(self, w=None):
+    def is_repetitive(self, w=None):
+    def infinite_repetitions(self, w=None):
+    def infinite_repetitions_bounded(self, w=None):
+    def infinite_repetitions_growing(self, w=None):
+    def reach(self, w):
+    def simplify(self, Z=None):
+    def simplify_injective(self):

Would it be possible to update the description of the ticket with this complete list?

[seblabbe]

comment:16

In particular, I am unsure about the choice of reach, simplify and simplify_injective. These names do not make me think about what it is. Can we find more evoking names? Possibly also for infinite_repetitions*.

[staroste]

comment:17

Replying to @seblabbe:

In particular, I am unsure about the choice of reach, simplify and simplify_injective. These names do not make me think about what it is. Can we find more evoking names? Possibly also for infinite_repetitions*.

The term simplification is used by A. Ehrenfeucht and G. Rozenberg, and maybe earlier. I'd prefer to keep it unless we find a much better name (I can't think of anything simple).
I don't know about reach, Martin?

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

da0536b

Replace reach with _language_naive

[sagetrac-git]

Changed commit from 9c216e0 to da0536b

[mrejmon]

comment:20

I "solved" the reach naming problem by replacing it with calls to _language_naive.

[seblabbe]

Thank you, the updated description helps me to have an easier overview of what it added.

I have few suggestions about the name of the methods. See below. It is important to choose them well, because they are harder to change once in sage because of backward compatibility.

Replying to new description:

Add the following methods to the WordMorphism class:

• is_injective() - injectivity test

okay

• is_unboundedly_repetitive() - whether the morphism is unboundedly repetitive, i.e. has a periodic point containing an unbounded letter, that is also a periodic word

okay

• is_pushy() - whether the morphism is pushy (its language contains an infinite amount of words with no growing letters)

okay

• is_repetitive() - whether the morphism (its language) contains arbitrarily large repetitions

okay

• infinite_repetitions() - finds the set of all words which are primitive roots of arbitrarily large repetitions in the language of the morphism

I rather suggest infinite_repetitions_primitive_roots(). Explicit is better and implicit. See import this in Python:)

• infinite_repetitions_bounded() - same as above, but only those words which contain no growing letters
• infinite_repetitions_growing() - same as above, but only those words which contain at least one growing letter

I would suggest to rename those two methods as hidden methods _infinite_repetitions_bounded() and _infinite_repetitions_growing(). Then, I would suggest to access those methods from the method infinite_repetitions() as follows:

• infinite_repetitions(growing_letters=None), the default
• infinite_repetitions(growing_letters=True), only those words which contain at least one growing letter
• infinite_repetitions(growing_letters=False), only those words which contain no growing letters

Of course, you will need to also add documentation about this new argument growing_letters.

• simplify() - returns a simplification of the morphism

I would suggest to rename it to simplify_alphabet_size(), because this is really what this methods wants to do: reduce the size of the alphabet while doing essentially the same thing.

• simplify_injective() - repeateadly calls simplify() until the result is injective

I suggest to rename it to simplify_to_injective() or even better simplify_until_injective() since the word until gives an hint about the procedure. Otherwise we don't know whether injective is a description of the input or the output. Here, it describes the output.

Review done during the Sage Thursdays in Bordeaux at https://wiki.sagemath.org/thursdaysbdx.

[seblabbe]

Reviewer: Sébastien Labbé

[sagetrac-git]

Changed commit from da0536b to 0d5f94a

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

02aaa8f	Rename simplify methods
0d5f94a	Merge infinite_repetitions* methods

[mrejmon]

comment:24

Thank you for the suggestions. I implemented all of them, except I named the parameter allow_growing instead of growing_letters and instead of hiding the infinite_repetitions_* methods I merged them into infinite_repetitions_primitive_roots, to remove some redundant code and docs.

[seblabbe]

comment:26

Positive review! Thanks for your work on this. Sorry for the delay.

[vbraun]

Changed branch from u/gh-mrejmon/18119 to 0d5f94a