Source code for stallings_graphs.about_TC_morphisms

# -*- coding: utf-8 -*-
r"""
The methods for the class ``FinitelyGeneratedSubgroup`` use a number of ancillary functions. These are the functions which deal with morphisms between free groups.

More precisely, morphisms and automorphisms are handled by Thierry Coulbois's ``train_track`` package. Here we provide mutual translations between objects of class ``Word``, as used in ``stallings_graphs``, and words as used in the ``train_track`` package. Specifically, we stick to words on a numerical alphabet (``alphabet_type='123'``) and to the ``train_track`` format ``type='x0'``.

The translation is as follows: if `i` is a positive integer, the corresponding letter is ``xj`` with `j = i-1`; if `i` is a negative integer, the corresponding letter is ``Xj`` with `j = -i-1`.


We have functions to:

- translate a character, or a word, from one of the formats to the other

- define a ``FGendomorphism``(this is a ``FreeGroupMorphism`` from ``train_track``), by giving the list of images of the ambient free group basis

- compute the image of a word (alphabetic or numeric) by a ``FGendomorphism``

We inherit the methods from ``train_track``, to compose morphisms, to check whether they are invertible and, if so, to compute their inverse.

EXAMPLES::

    sage: from stallings_graphs.about_TC_morphisms import FGendomorphism
    sage: L = ['ab','a']
    sage: phi = FGendomorphism(L,alphabet_type='abc')
    sage: phi
    Morphism from Free Group on generators {x0, x1} to Free Group on generators {x0, x1}: x0->x0*x1,x1->x0
    
::
    
    sage: from stallings_graphs.about_TC_morphisms import image_of_Word_by_endomorphism
    sage: w = 'abAbA'
    sage: image_of_Word_by_endomorphism(phi, w, alphabet_type='abc')
    word: abaBBA


AUTHOR:

- Pascal WEIL, CNRS, Univ. Bordeaux, LaBRI <pascal.weil@cnrs.fr> (2019-04-04): initial version.

"""

# from sage.misc.prandom import randint
from sage.combinat.words.word import Word
#from sage.graphs.digraph import DiGraph
#from sage.sets.disjoint_set import DisjointSet
#from sage.misc.latex import LatexExpr
#
#from partial_injections import PartialInjection

[docs]def translate_numeric_to_x0_character(i): r""" Return the corresponding character in Thierry Coulbois's ``x0`` format. ``i`` is expected to be a non-zero integer. An exception is raised if that is not the case. INPUT: - ``i`` -- integer OUTPUT: - string EXAMPLES:: sage: from stallings_graphs.about_TC_morphisms import translate_numeric_to_x0_character sage: translate_numeric_to_x0_character(7) 'x6' :: sage: translate_numeric_to_x0_character(-7) 'X6' """ if i > 0: return "x%s" % (i-1) elif i < 0: return "X%s" % (-i-1) else: raise ValueError('the argument is not a proper numerical character')
[docs]def translate_x0_character_to_numeric(letter): r""" Return the corresponding numeric. ``letter`` is expected to be a string of the form ``xj`` or ``Xj``, where ``j`` is a non-negative integer in decimal expansion. INPUT: - ``letter`` -- string OUTPUT: - integer EXAMPLES:: sage: from stallings_graphs.about_TC_morphisms import translate_x0_character_to_numeric sage: translate_x0_character_to_numeric('x100') 101 :: sage: translate_x0_character_to_numeric('X100') -101 """ i = int(letter[1:]) if letter[0] == 'x': return i + 1 elif letter[0] == 'X': return -i-1 else: raise ValueError('the argument is not a proper letter')
[docs]def translate_numeric_Word_to_x0_list(w): r""" Return the corresponding word in Thierry Coulbois's ``x0`` format. ``w`` is expected to be a ``Word`` on a numerical alphabet. INPUT: - ``w`` -- Word OUTPUT: - list EXAMPLES:: sage: from stallings_graphs.about_TC_morphisms import translate_numeric_Word_to_x0_list sage: translate_numeric_Word_to_x0_list([7,1,-2,3,-3]) ['x6', 'x0', 'X1', 'x2', 'X2'] """ if len(w) == 0: return [] u = [translate_numeric_to_x0_character(x) for x in w] return u
[docs]def translate_x0_word_to_numeric_Word(u): r""" Return the corresponding numeric Word. ``u`` is expected to be a ``FreeGroup`` element in the sense of the ``train_track`` package, written with letters of the form ``xj`` or ``Xj``, where ``j`` is a non-negative integer in decimal expansion. INPUT: - ``u`` -- element of type ``train_track.free_group.FreeGroup_class_with_category.element_class`` (the free group elements in the ``train_track`` package) OUTPUT: - ``Word`` EXAMPLES:: sage: from train_track import FreeGroupMorphism sage: D = {'x0':['x0','x1'],'x1':['X0']} sage: phi = FreeGroupMorphism(D) sage: print(phi) x0->x0*x1,x1->x0^-1 sage: w = phi(['X0','x1','x0']) sage: from stallings_graphs.about_TC_morphisms import translate_x0_word_to_numeric_Word sage: translate_x0_word_to_numeric_Word(w) word: -2,-1,2 :: sage: w = phi([]) sage: translate_x0_word_to_numeric_Word(w) word: """ if len(u) == 0: return Word([]) v = u.to_word() w = [] for i in range(len(v)): a,b = (v[i][0],int(v[i][1:])) if a == 'x': w = w + [b+1] elif a == 'X': w = w + [-b-1] else: raise ValueError('Something went wrong: the letters of this x0-word should be strings starting with "x" or "X".') return Word(w)
[docs]def FGendomorphism(L, alphabet_type='abc'): r""" Return a ``FreeGroupMorphism`` in the sense of the ``train_track`` package, defined by the given list. ``L`` is expected to be a list of objects of class Word, on a numerical or letter alphabet according to the value of ``alphabet_type``. INPUT: - ``L`` -- list of objects of class Word - ``alphabet_type`` -- string, which is either ``'123'`` or ``'abc'`` OUTPUT: - ``FreeGroupMorphism`` EXAMPLES:: sage: from stallings_graphs.about_TC_morphisms import FGendomorphism sage: L = ['ab','a'] sage: phi = FGendomorphism(L,alphabet_type='abc') sage: phi Morphism from Free Group on generators {x0, x1} to Free Group on generators {x0, x1}: x0->x0*x1,x1->x0 """ from train_track import FreeGroupMorphism from stallings_graphs.about_words import translate_alphabetic_Word_to_numeric if alphabet_type == 'abc': numerical_list = [translate_alphabetic_Word_to_numeric(w) for w in L] elif alphabet_type == '123': numerical_list = L else: raise ValueError('the "alphabet_type" argument is neither "123" nor "abc".') # translated_list = [translate_numeric_Word_to_x0_list(w) for w in numerical_list] prepare_phi = {} for i in range(len(L)): prepare_phi['x%s' % i] = translated_list[i] # return FreeGroupMorphism(prepare_phi)
[docs]def image_of_Word_by_endomorphism(phi, w, alphabet_type='abc'): r""" Return the image of the second argument by the first. INPUT: - ``phi`` -- ``FreeGroupMorphism`` - ``w`` -- a ``Word`` on a numeric or letter alphabet, depending on the value of ``alphabet_type`` - ``alphabet_type`` -- string, which is either ``'123'`` or ``'abc'`` OUTPUT: - ``Word`` EXAMPLES:: sage: from stallings_graphs.about_TC_morphisms import image_of_Word_by_endomorphism sage: from stallings_graphs.about_TC_morphisms import FGendomorphism sage: L = ['ab','a'] sage: phi = FGendomorphism(L,alphabet_type='abc') sage: w = 'abAbA' sage: image_of_Word_by_endomorphism(phi, w, alphabet_type='abc') word: abaBBA """ from stallings_graphs.about_words import translate_alphabetic_Word_to_numeric, translate_numeric_Word_to_alphabetic if alphabet_type == 'abc': numerical_word = translate_alphabetic_Word_to_numeric(w) elif alphabet_type == '123': numerical_word = w else: raise ValueError('the "alphabet_type" argument must be either "123" or "abc" (and is not).') # translated_word = translate_numeric_Word_to_x0_list(numerical_word) image_to_be_translated = phi(translated_word) image = translate_x0_word_to_numeric_Word(image_to_be_translated) if alphabet_type == 'abc': image = translate_numeric_Word_to_alphabetic(image) return image