Ancillary functions about words

The methods for the class FinitelyGeneratedSubgroup use a number of ancillary functions. These are the functions which deal with words (actually, objects of class Word) in the context of group theory.

A word is a string of characters from either a numerical or an alphabetical set of letters: alphabet_type='123' or 'abc'

alphabet_type='123': The positive letters form an interval \([1,r]\). Their inverses (a.k.a. negative letters) are the corresponding negative integers. The symmetrized alphabet is the union of positive and negative letters (zero is NOT a letter). The \(\textit{rank}\) of a word is the maximal absolute value of a letter occurring in the word. When represented in a (say LaTeX) file (.tex, .pdf), the letters are written \(a_i\).

alphabet_type='abc': positive letters are lower case (at most 26 letters, \(a\):\(z\)) and their inverses are the corresponding upper case letters (\(A\):\(Z\)).

We have functions to:

  • translate a word or a list of words from one alphabet_type to the other
  • test whether a word of alphabet_type '123' is (freely) reduced or cyclically reduced
  • freely reduce a word of alphabet_type '123'
  • computes the cyclic reduction of a word of alphabet_type '123'
  • produce a random word of alphabet_type '123' of given length on an alphabet of given rank (given a positive integer \(r\)).

EXAMPLES:

sage: from stallings_graphs.about_words import group_inverse
sage: w = Word('aBabbaBA')
sage: group_inverse(w,alphabet_type='abc')
word: abABBAbA
sage: from stallings_graphs.about_words import free_group_reduction
sage: w = Word([3,1,-2,-2,2,1,-1,2,5,-3])
sage: free_group_reduction(w)
word: 3,1,5,-3
sage: from stallings_graphs.about_words import random_reduced_word
sage: w = random_reduced_word(7,3)   #random
Word([2,-1,3,-1,-1,2,-3])

AUTHOR:

  • Pascal WEIL, CNRS, Univ. Bordeaux, LaBRI <pascal.weil@cnrs.fr> (2018-06-09): initial version.
stallings_graphs.about_words.alphabetic_inverse(x)[source]

Return the inverse of an alphabetic letter.

\(x\) is expected to be a character in \(a\):\(z\) or \(A\):\(Z\). Taking the inverse toggles between upper and lower case letters.

INPUT:

  • x – character

OUTPUT:

  • character

EXAMPLES:

sage: from stallings_graphs.about_words import alphabetic_inverse
sage: alphabetic_inverse('b')
'B'
sage: alphabetic_inverse('D')
'd'
stallings_graphs.about_words.cyclic_reduction_of_a_word(u)[source]

Return the elements of the cyclically reduced decomposition of this word.

\(u\) is expected to be a Word on a numerical alphabet. The cyclically reduced decomposition of \(u\) is the pair of Words \((v,w)\) such that \(v\) is cyclically reduced, and \(u = w^{-1}vw\).

INPUT:

  • wWord
  • check – boolean

OUTPUT:

  • pair of objects of class Word

EXAMPLES

sage: from stallings_graphs.about_words import cyclic_reduction_of_a_word
sage: u = Word([1,-2,-2,-1,1])
sage: cyclic_reduction_of_a_word(u)
(word: 1,-2,-2, word: )
sage: u = Word([1,-2,1,-2,1,2,-1])
sage: cyclic_reduction_of_a_word(u)
(word: 1,-2,1, word: 2,-1)
sage: u = Word([1,-2,1,-1,1])
sage: cyclic_reduction_of_a_word(u)
(word: 1,-2,1, word: )
sage: u = Word([1,2,-2,-1,2,2,1,-1,-2])
sage: cyclic_reduction_of_a_word(u)
(word: 2, word: )
sage: u = Word()
sage: cyclic_reduction_of_a_word(u)
(word: , word: )
stallings_graphs.about_words.free_group_reduction(w, check=False)[source]

Return the reduced word that is equivalent to this word.

\(w\) is expected to be a Word on a numerical alphabet. The option check = True verifies that this is the case. The reduced word equivalent to a word \(w\) is obtained from \(w\) by repeatedly deleting pairs of consecutive letters which are mutually inverse.

INPUT:

  • wWord
  • check – boolean

OUTPUT:

  • Word

EXAMPLES

sage: from stallings_graphs.about_words import free_group_reduction
sage: w = Word([3,1,-2,-2,2,1,-1,2,5,-3])
sage: free_group_reduction(w)
word: 3,1,5,-3

ALGORITHM:

This method implements the classical algorithm, based on the usage of a pushdown automaton.

stallings_graphs.about_words.group_inverse(w, alphabet_type='123', check=False)[source]

Return the (free group) inverse of a word.

\(w\) is expected to be a Word on a numerical or letter alphabet, depending on the value of alphabet_type. Its inverse is obtained in reading \(w\) in reverse order and replacing each letter by its inverse. If check is set to True, is_valid_Word is run on \(w\).

INPUT:

  • wWord
  • alphabet_type – string, which must be either 'abc' or '123'

OUTPUT:

  • Word

EXAMPLES

sage: from stallings_graphs.about_words import group_inverse
sage: w = Word([3,1,-9,-2,5])
sage: group_inverse(w)
word: -5,2,9,-1,-3
sage: w = Word([-1,1,2,-2])
sage: group_inverse(w)
word: 2,-2,-1,1
sage: w = Word([1])
sage: group_inverse(w)
word: -1
sage: w = Word()
sage: group_inverse(w)
word: 
stallings_graphs.about_words.inverse_letter(i)[source]

Return the inverse of this (numerical) letter.

\(i\) is expected to be a non-zero integer.

INPUT:

  • i – integer

OUTPUT:

  • integer

EXAMPLES:

sage: from stallings_graphs.about_words import inverse_letter
sage: inverse_letter(3)
-3
sage: inverse_letter(-4)
4
stallings_graphs.about_words.is_cyclically_reduced(w, check=False)[source]

Return whether this word is cyclically reduced.

\(w\) is expected to be a Word on a numerical alphabet. The option check verifies that it is the case. A word is cyclically reduced if it is reduced and its first and last letters are not mutually inverse.

INPUT:

  • wWord
  • check – boolean

OUTPUT:

  • boolean

EXAMPLES

sage: from stallings_graphs.about_words import is_cyclically_reduced
sage: w = Word([3,1,-2,-2,5,-3])
sage: is_cyclically_reduced(w)
False
sage: u = Word([3,1,-2,-2,5,3])
sage: is_cyclically_reduced(u)
True
stallings_graphs.about_words.is_reduced(w, check=False)[source]

Return whether this word is a reduced.

\(w\) is expected to be a Word on a numerical alphabet. A word \(w\) is reduced (in the group-theoretic sense) if it does not contain consecutive letters which are mutually inverse. The option check verifies whether \(w\) is a valid Word.

INPUT:

  • wWord
  • check – boolean

OUTPUT:

  • boolean

EXAMPLES

sage: from stallings_graphs.about_words import is_reduced
sage: w = Word([3,1,-2,-2,5,-3])
sage: is_reduced(w)
True
sage: u = Word([3,1,-2,2,5,-3])
sage: is_reduced(u)
False
stallings_graphs.about_words.is_valid_Word(w, alphabet_type='123')[source]

Return whether a Word is valid, in the sense of having a consistent alphabet.

\(w\) is expected to be a Word. It is \(\textit{valid}\) if all its letters are non-zero integers if alphabet_type='123'; or are in \(a\):\(z\) \(+\) \(A\):\(Z\) if alphabet_type='abc'.

INPUT:

  • wWord
  • alphabet_type – string, which must be either 'abc' or '123'

OUTPUT:

  • boolean

EXAMPLES:

sage: from stallings_graphs.about_words import is_valid_Word
sage: w = Word([2,-1,-2,3,1,3])
sage: is_valid_Word(w)
True
sage: is_valid_Word(Word('bABcac'), alphabet_type='abc')
True
sage: is_valid_Word(Word([2,-1,-2,0,1,3]))
False
stallings_graphs.about_words.is_valid_list_of_Words(L, alphabet_type='123')[source]

Return whether a list of Words is valid, in the sense of is_valid_Word.

\(L\) is expected to be a list of objects of class Word. It is valid if all its components satisfy is_valid_Word.

INPUT:

  • LList of objects of the class Word
  • alphabet_type – string, which must be either 'abc' or '123'

OUTPUT:

  • boolean

EXAMPLES:

sage: from stallings_graphs.about_words import is_valid_list_of_Words
sage: L = [Word([2,-1,-2,3,1,3]), Word([1,2,-3,1,-1])]
sage: is_valid_list_of_Words(L)
True
::
sage: L = [Word(‘bABcac’),’abcBA’,’baaCB’] sage: is_valid_list_of_Words(L, alphabet_type=’abc’) True
stallings_graphs.about_words.negative_letters(r)[source]

Return the set of negative (numerical) letters up to \(-r\).

\(r\) is expected to be positive.

INPUT:

  • r – integer

OUTPUT:

  • the list of integers from \(-1\) to \(-r\)

EXAMPLES:

sage: from stallings_graphs.about_words import negative_letters
sage: negative_letters(6)
[-1, -2, -3, -4, -5, -6]
stallings_graphs.about_words.positive_alphabetic_content(w, check=False)[source]

Return the set of positive letters which occur, or their inverse occurs in \(w\).

\(w\) is expected to be a Word on a numerical alphabet. If check is True, is_valid_Word(w,alphabet_type='123') is run.

INPUT:

  • wWord
  • check – Boolean

OUTPUT:

  • list of positive integers

EXAMPLES:

sage: from stallings_graphs.about_words import positive_alphabetic_content
sage: w = Word([3,1,-2,-2,5,-3])
sage: positive_alphabetic_content(w)
{1, 2, 3, 5}
sage: w = Word([])
sage: positive_alphabetic_content(w)
set()
stallings_graphs.about_words.positive_letters(r)[source]

Return the list of positive (numerical) letters up to \(r\).

\(r\) is expected to be positive.

INPUT:

  • r – integer

OUTPUT:

  • list

EXAMPLES:

sage: from stallings_graphs.about_words import positive_letters
sage: positive_letters(6)
[1, 2, 3, 4, 5, 6]
stallings_graphs.about_words.positive_value(i)[source]

Return the positive value of a (numerical) letter.

\(i\) is expected to be a non-zero integer.

INPUT:

  • i – integer

OUTPUT:

  • integer

EXAMPLES:

sage: from stallings_graphs.about_words import positive_value
sage: positive_value(3)
3
sage: positive_value(-4)
4
stallings_graphs.about_words.random_letter(r)[source]

Return a random letter in the symmetric alphabet of this size.

\(r\) is expected to be a positive integer. The symmetric alphabet of size \(r\) is the set of non-zero integers between \(-r\) and \(r\). The probability distribution is uniform.

INPUT:

  • r – integer

OUTPUT:

  • integer

EXAMPLES

sage: from stallings_graphs.about_words import random_letter
sage: random_letter(4)   # random
2
stallings_graphs.about_words.random_reduced_word(n, r)[source]

Return a random reduced word of length \(n\) in the symmetric alphabet of size \(r\).

\(n\) is expected to be a non-negative integer and \(r\) is expected to be a positive integer. A word is reduced if it does not contain consecutive letters which are mutually inverse. The probability distribution is uniform.

INPUT:

  • n – integer
  • r – integer

OUTPUT:

  • Word

EXAMPLES

sage: from stallings_graphs.about_words import random_reduced_word
sage: random_reduced_word(4,5)   # random
Word([2,-1,3,-4,-1])
stallings_graphs.about_words.random_word(n, r)[source]

Return a random word of length \(n\) in the symmetric alphabet of size \(r\).

\(n\) is expected to be a non-negative integer and \(r\) is expected to be a positive integer. The word produced on the symmetric alphabet of size \(r\) is not necessarily reduced. The probability distribution is uniform.

INPUT:

  • n – integer
  • r – integer

OUTPUT:

  • Word

EXAMPLES

sage: from stallings_graphs.about_words import random_word
sage: random_word(4,5)   # random
Word([2,-1,3,-4,-1])
stallings_graphs.about_words.rank(w, check=False)[source]

Return the least rank of a free group containing this Word.

\(w\) is expected to be a Word on a numerical alphabet. The least rank of a free group containing \(w\) is the max of the positive values of its letters. If check is True, is_valid_Word(w,alphabet_type='123') is run.

INPUT:

  • wWord
  • check – boolean

OUTPUT:

  • integer

EXAMPLES:

sage: from stallings_graphs.about_words import rank
sage: w = Word([3,1,-2,-2,5,-3])
sage: rank(w)
5
sage: w = Word([])
sage: rank(w)
0
stallings_graphs.about_words.symmetric_alphabet(r)[source]

Return the full symmetric (numerical) alphabet.

\(r\) is expected to be positive.

INPUT:

  • r – integer

OUTPUT:

  • the list of integers from \(1\) to \(r\) and from \(-1\) to \(-r\)

EXAMPLES:

sage: from stallings_graphs.about_words import symmetric_alphabet
sage: symmetric_alphabet(6)
[1, 2, 3, 4, 5, 6, -1, -2, -3, -4, -5, -6]
stallings_graphs.about_words.translate_alphabetic_Word_to_numeric(w)[source]

Return the numerical equivalent of a Word of alphabet_type = 'abc'.

\(w\) is expected to be a Word on alphabet \(a\):\(z\) \(+\) \(A\):\(Z\). The output is a Word on alphabet \(\{\pm 1, ..., \pm 26\}\).

INPUT:

  • wWord

OUTPUT:

  • Word

EXAMPLES:

sage: from stallings_graphs.about_words import translate_alphabetic_Word_to_numeric
sage: translate_alphabetic_Word_to_numeric(Word('aBBaAc'))
word: 1,-2,-2,1,-1,3
sage: translate_alphabetic_Word_to_numeric(Word(''))
word:
sage: translate_alphabetic_Word_to_numeric(Word([]))
word:
stallings_graphs.about_words.translate_character_to_numeric(x)[source]

Return the numeric equivalent of a character in \(a\):\(z\) or \(A\):\(Z\).

\(x\) is expected to be a character in \(a\):\(z\) or \(A\):\(Z\). The numeric equivalent is 1-26 for \(a\):\(z\) and the opposite for \(A\):\(Z\).

INPUT:

  • x – character

OUTPUT:

  • integer

EXAMPLES:

sage: from stallings_graphs.about_words import translate_character_to_numeric
sage: translate_character_to_numeric('b')
2
sage: translate_character_to_numeric('D')
-4
stallings_graphs.about_words.translate_numeric_Word_to_alphabetic(w)[source]

Return the alphabetic equivalent of a numeric word.

\(w\) is expected to be a Word on a numerical alphabet \(\{\pm 1, \dots, \pm 26\}\). The output is a Word on alphabet \(a\):\(z\) \(+\) \(A\):\(Z\).

INPUT:

  • wWord

OUTPUT:

  • Word

EXAMPLES:

sage: from stallings_graphs.about_words import translate_numeric_Word_to_alphabetic
sage: translate_numeric_Word_to_alphabetic(Word([2,-1,-2,3,1,3]))
word: bABcac
stallings_graphs.about_words.translate_numeric_to_character(x)[source]

Return the character equivalent of a numerical letter.

\(x\) is expected to be a non-zero integer in the interval \([-26;26]\). A ValueError is raised otherwise. The numeric equivalent is a lower case character if \(x > 0\) and an upper case character otherwise.

INPUT:

  • x – integer

OUTPUT:

  • character

EXAMPLES:

sage: from stallings_graphs.about_words import translate_numeric_to_character
sage: translate_numeric_to_character(16)
'p'
sage: translate_numeric_to_character(-10)
'J'