Ancillary functions about automata

The methods for the class FinitelyGeneratedSubgroup use a number of ancillary functions. These are the functions which deal with graphs and automata, 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\)).

Automata are objects of class DiGraph whose edge labels are positive letters (always numerical). When automata are visualized, the value of alphabet_type determines how these edge labels will appear. In most cases, the vertex set of a DiGraph is a set of integers, usually of the form \([0..n]\).

We have functions to:

  • compute the bouquet of a list of Word (of alphabet_type '123' or 'abc')
  • extract from a DiGraph the list of its transitions (one for each letter labeling an edge)
  • determine whether a DiGraph is deterministic and in that case, compute the transition functions (one for each letter labeling an edge)
  • determine whether a DiGraph is folded and in that case, compute the corresponding tuple of partial injections (objects of class PartialInjection)
  • relabel vertices
  • permute the names of two vertices
  • normalize its vertex set (so it is \([0..n]\))
  • compute the image of a word in a DiGraph
  • prune a DiGraph
  • cyclically reduce a DiGraph
  • compute the fibered product of two objects of class DiGraph
  • prepare a rooted DiGraph to be visualized using TikzPicture with alphabet_type '123' or 'abc'
  • show a rooted DiGraph (using graph.plot), with the root in a different color

EXAMPLES:

sage: from stallings_graphs.about_words import random_reduced_word
sage: L = ['aBABBaaaab', 'BBAbbABABA', 'bbAbAbaabb']
sage: from stallings_graphs.about_automata import bouquet
sage: G = bouquet(L, alphabet_type='abc')
sage: from stallings_graphs.about_folding import NT_fold
sage: GG = NT_fold(G)
sage: GG
Looped multi-digraph on 23 vertices

AUTHOR:

stallings_graphs.about_automata.DiGraph_to_list_of_PartialInjection(G)[source]

Return the list of partial injections (in fact: objects of class PartialInjection) on the set of vertices of this graph.

G is expected to be a folded DiGraph (a ValueError is raised otherwise) with edge labels in \([1..r]\) and vertex set equal to \([0..n-1]\) (\(r\) and \(n\) not given). Folded means that the graph is deterministic and co-deterministic or, equivalently, that every edge label defines a partial injection on the vertex set. The list returned has size \(r\), and represents the partial injections (from the class PartialInjection) induced by edge labels \(1, 2, \dots, r\), respectively.

INPUT:

  • GDiGraph

OUTPUT:

  • List of lists

EXAMPLES

sage: from stallings_graphs import PartialInjection
sage: from stallings_graphs.about_automata import bouquet, DiGraph_to_list_of_PartialInjection
sage: from stallings_graphs.about_folding import NT_fold
sage: from stallings_graphs import PartialInjection
sage: L = [[3,1,-2,-1,-3],[-1,2,-1,-2,1,2],[3,2,-3,-3,1]]
sage: G = bouquet(L)
sage: GG = NT_fold(G)
sage: DiGraph_to_list_of_PartialInjection(GG)
[A partial injection of size 10, whose domain has size 4,
 A partial injection of size 10, whose domain has size 5,
 A partial injection of size 10, whose domain has size 3]
sage: L = [[3,1,-2,-1,-3],[-1,2,-1,-2,1,2],[3,2,-3,-3,1],[5]]
sage: G = bouquet(L)
sage: GG = NT_fold(G)
sage: DiGraph_to_list_of_PartialInjection(GG)
[A partial injection of size 10, whose domain has size 4,
 A partial injection of size 10, whose domain has size 5,
 A partial injection of size 10, whose domain has size 3,
 A partial injection of size 10, whose domain has size 0,
 A partial injection of size 10, whose domain has size 1]
stallings_graphs.about_automata.are_equal_as_rooted_unlabeled(G, H, certificate=False, verbose=False)[source]

Return whether two folded DiGraph are the Stallings graphs of the same subgroup, possibly with different vertex labels.

The two first arguments are expected to be folded DiGraph. They represent the same subgroup if the corresponding tuples of PartialInjection coincide, up to a relabeling of the vertices which fixes the base vertex (vertex 0). That is: if the partial injections defining the second argument are obtained by conjugating the partial injections defining the first argument by a permutation which fixes 0. In verbose mode: details are given as to why the graphs do not represent the same subgroup or, if they do, which permutation fixing 0 maps one to the other. In certificate mode: if the subgroups are the same, the output is (True,sigma) where sigma is a conjugating permutation; otherwise the output is (False,None).

INPUT:

  • GDiGraph
  • HDiGraph
  • certificate – boolean
  • verbose – boolean

OUTPUT: If certificate is set to False:

  • a boolean, if certificate is set to False; and if certificate is set to True, a tuple of the form (False,None) or (True,sigma) where sigma is the conjugating permutation

EXAMPLES

sage: from stallings_graphs import FinitelyGeneratedSubgroup, PartialInjection
sage: from stallings_graphs.about_automata import are_equal_as_rooted_unlabeled
sage: L1 = [PartialInjection([1,2,None,4,5,3]), PartialInjection([0,3,4,None,None,None])]
sage: H1 = FinitelyGeneratedSubgroup(L1)
sage: G1 = H1.stallings_graph()
sage: L2 = [PartialInjection([1,2,None,5,4,3]), PartialInjection([0,3,5,None,None,None])]
sage: H2 = FinitelyGeneratedSubgroup(L2)
sage: G2 = H2.stallings_graph()
sage: L3 = [PartialInjection([1,2,None,4,5,3]), PartialInjection([0,5,3,None,None,None])]
sage: H3 = FinitelyGeneratedSubgroup(L3)
sage: G3 = H3.stallings_graph()
sage: are_equal_as_rooted_unlabeled(G1,G2)
False
sage: are_equal_as_rooted_unlabeled(G1,G3)
True
sage: (b, tau) = are_equal_as_rooted_unlabeled(G1,G3,certificate=True)
sage: tau
[0, 1, 2, 5, 3, 4]
sage: H = FinitelyGeneratedSubgroup([])
sage: G1 = H.stallings_graph()
sage: K = FinitelyGeneratedSubgroup.from_generators([])
sage: G2 = K.stallings_graph()
sage: b,tau = are_equal_as_rooted_unlabeled(G1,G2,certificate=True)
sage: (b,tau)
(True, [0])
sage: H1 = FinitelyGeneratedSubgroup.from_generators(['a','b'],alphabet_type='abc')
sage: G1 = H1.stallings_graph()
sage: H2 = FinitelyGeneratedSubgroup.from_generators(['ab','ba','aba'],alphabet_type='abc')
sage: G2 = H2.stallings_graph()
sage: are_equal_as_rooted_unlabeled(G1,G2)
True

ALGORITHM:

One first checks whether both inputs represent subgroups in the same free group (same maximum value of a label) and have the same size (number of vertices). Then whether there is a permutation of the vertices other than the base vertex (vertex 0) which maps each transition (a partial injection) of the first argument to the corresponding partial injection of the second. Since a True output is least likely, the algorithm eliminates the most common and superficial reason for not being the same: different profiles of partial injections (ordered lists of lengths of sequences, resp. cycles, in the two subgroups. Then the algorithm attempts to build a conjugating permutation (unique if it exists). This results in a long code, experimentally much faster to run (on randomly generated subgroups constructed to be conjugated) than the shorter code relying on labeled graph isomorphism.

stallings_graphs.about_automata.bouquet(list_of_Words, alphabet_type='123', check=False)[source]

Return the bouquet of loops labeled by this list of words.

list_of_Words is expected to be a List of objects of class Word on a symmetric alphabet which is numerical (alphabet_type = '123') or consists of letters (alphabet_type = 'abc'). The option check = True verifies that this argument is a valid list of Word over the given alphabet_type. The bouquet in question is a DiGraph with vertex set of the form \([0..n]\), where every word in list_of_Words labels a loop at vertex 0. The edges are labeled by letters from the symmetric alphabet.

INPUT:

  • list_of_Words – List of Word
  • alphabet_type – string, which is either '123' or 'abc'
  • check – boolean

OUTPUT:

  • DiGraph

EXAMPLES:

sage: from stallings_graphs.about_automata import bouquet, transitions
sage: L = [[4,1,1,-4], [-4, -2, -1, 2, -1],[4]]
sage: G = bouquet(L)
sage: G
Looped multi-digraph on 8 vertices
sage: GG = bouquet([[-1]])
sage: GG
Looped multi-digraph on 1 vertex
stallings_graphs.about_automata.cyclic_reduction(G, trace=False)[source]

Return the cyclic reduction of this DiGraph.

G is expected to be a DiGraph with numerical edge labels and vertex set of the form \([0..n]\). The cyclic reduction is obtained by iteratively deleting vertices of degree 1 (including the base vertex – that is the difference with the prune method). Its vertex set is normalized to be of the form \([0..m]\). Note that the vertex labeled \(0\) in the cyclic reduction need not be the same as in the G (but it will be the same if the base vertex of \(G\) belongs to the cyclic reduction). If trace is set to True, the output includes, in addition to the cyclic reduction of G, the Word which labels the shortest path from vertex 0 to a vertex that is preserved in the algorithm.

INPUT:

  • GDiGraph
  • trace– boolean

OUTPUT:

  • a Digraph if trace is set to False; and a pair (GG, w) of a DiGraph and a Word otherwise.

EXAMPLES:

sage: from stallings_graphs import FinitelyGeneratedSubgroup
sage: from stallings_graphs.about_automata import cyclic_reduction, pruning, normalize_vertex_names
sage: L = ['ababA', 'aBabbabA', 'aababABAA']
sage: H = FinitelyGeneratedSubgroup.from_generators(L, alphabet_type='abc')
sage: G = H.stallings_graph()
sage: G
Looped multi-digraph on 6 vertices
sage: G2 = cyclic_reduction(G)
sage: G2
Looped multi-digraph on 5 vertices
sage: G2,w = cyclic_reduction(G,trace=True)
sage: w
word: 1
stallings_graphs.about_automata.exchange_labels(G, i, j)[source]

Exchanges the given vertex names in this DiGraph.

G is expected to be a DiGraph with vertices \(0,\dots,n-1\), and i, j are expected to be vertices of \(G\). Outputs an isomorphic DiGraph, where the names of the vertices \(i\) and \(j\) have been exchanged.

INPUT:

  • GDiGraph
  • i – integer
  • j – integer

OUTPUT:

  • DiGraph

EXAMPLES:

sage: from stallings_graphs.about_automata import exchange_labels
sage: G = DiGraph([[0,1,2,3,4],[(0,0,1), (0,1,2), (0,4,3), (1,0,2), (1,2,1), (1,2,3), (2,3,2), (2,3,3), (4,3,1)]], format='vertices_and_edges', loops=True, multiedges=True)
sage: G = exchange_labels(G,0,3)
sage: G
Looped multi-digraph on 5 vertices
stallings_graphs.about_automata.fibered_product(G1, G2)[source]

Compute the fibered product (a.k.a. direct product) of two edge-labeled graphs.

G1 and G2 are assumed to be of class DiGraph, with edges labeled by positive integers. Their fibered product is the DiGraph whose vertex set is the Cartesian product of the sets of vertices of G1 and G2 and whose edges are as follows: there is an \(a\)-labeled edge from \((u_1,u_2)\) to \((v_1,v_2)\) if and only if G1 has an \(a\)-labeled edge from \(u_1\) to \(v_1\) and G2 has an \(a\)-labeled edge from \(u_2\) to \(v_2\).

INPUT:

  • G1DiGraph
  • G2DiGraph

OUTPUT:

  • DiGraph

EXAMPLES

sage: from stallings_graphs.about_automata import fibered_product
sage: V1 = range(3)
sage: E1 = [(i,j,abs(i-j)) for i in V1 for j in V1]
sage: G1 = DiGraph([V1,E1], format='vertices_and_edges', loops=True, multiedges=True)
sage: V2 = range(3)
sage: E2 = [(i,j,abs(i-j+1)) for i in V2 for j in V2]
sage: G2 = DiGraph([V2,E2], format='vertices_and_edges', loops=True, multiedges=True)
sage: G12 = fibered_product(G1,G2)
sage: G12.vertices()
[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]
sage: len(G12.edges())
26
stallings_graphs.about_automata.image_of_word(G, w, qinitial=0, trace=False)[source]

Return the vertex reached after reading this word in this graph (None if it cannot be read).

G is expected to be a DiGraph whose edges are labeled deterministically and codeterministically (folded DiGraph) by a numerical alphabet (typically, G is a Stallings graph) [not verified], w is a Word on a numerical alphabet and qinitial is a vertex of G. If one can read w from qinitial in G, the output is the vertex reached. If one cannot, the output is None. The option trace=True documents the situation if w cannot be read in G: the output is the triple (None, length_read, last_vertex_visited) where length_read is the length of the longest prefix u of w which can be read in G starting at qinitial and last_vertex_visited is the vertex reached after reading u.

INPUT:

  • GDiGraph
  • wWord
  • qinitial – integer (state of G)
  • trace – boolean

OUTPUT:

  • integer or None if trace=False; and if trace=True, a triple consisting of three integers or None and two integers

EXAMPLES

sage: from stallings_graphs import FinitelyGeneratedSubgroup
sage: from stallings_graphs.about_automata import image_of_word
sage: L = ['ab','ba', 'aBaa']
sage: H = FinitelyGeneratedSubgroup.from_generators(L, alphabet_type = 'abc')
sage: G = H.stallings_graph()
sage: w = Word([1,-2,1,-1,1])
sage: image_of_word(G,w, qinitial = 0,trace = True)
(2, 5, 2)
sage: image_of_word(G,w)
2
sage: ww = Word([1,2,-1,-2])
sage: image_of_word(G,ww)
0
sage: w = Word([2,2,-1])
sage: image_of_word(G,w, qinitial = 0,trace = True)
(None, 1, 2)
sage: image_of_word(G,w) is None
True
sage: w = Word()
sage: image_of_word(G,w, qinitial = 0,trace = True)
(0, 0, 0)
sage: H = FinitelyGeneratedSubgroup([])
sage: G = H.stallings_graph()
sage: w = Word([2,2,-1])
sage: image_of_word(G,w, qinitial = 0,trace = True)
(None, 0, 0)
sage: w = Word()
sage: image_of_word(G,w, qinitial = 0,trace = True)
(0, 0, 0)
stallings_graphs.about_automata.is_deterministic(digr)[source]

Return whether this DiGraph is deterministic.

digr is expected to be a DiGraph with labeled edges and with vertex set of the form \([0..n]\). It is said to be deterministic if for each vertex \(v\) and each label \(a\), there is at most one \(a\)-labeled edge out of \(v\).

INPUT:

  • digrDiGraph

OUTPUT:

  • boolean

EXAMPLES

sage: from stallings_graphs.about_automata import bouquet, is_deterministic
sage: L = [[3,1,1,-3], [-3, -2, -1, 2, -1]]
sage: digr = bouquet(L)
sage: is_deterministic(digr)
False
stallings_graphs.about_automata.is_folded(G)[source]

Return whether this DiGraph is folded (deterministic and co-deterministic).

G is expected to be a DiGraph with labeled edges and with vertex set of the form \([0..n]\). It is said to be deterministic if for each vertex \(v\) and each label \(a\), there is at most one \(a\)-labeled edge out of \(v\); and co-deterministic if for each vertex \(v\) and label \(a\), there is at most one \(a\)-labeled edge into \(v\).

INPUT:

  • GDiGraph

OUTPUT:

  • boolean

EXAMPLES

sage: from stallings_graphs.about_automata import bouquet, is_folded
sage: L = [[-3,1,2,1], [3,2,1]]
sage: G = bouquet(L)
sage: is_folded(G)
False
stallings_graphs.about_automata.normalize_vertex_names(G)[source]

Rename the vertices of this DiGraph so they are of the form \([0..n-1]\).

G is expected to be a DiGraph with vertex set a set of integers (or at least sortable elements). The output DiGraph is isomorphic to G, with vertices labeled \([0..n-1]\), where the new vertex names respect the original order on vertex identifiers.

INPUT:

  • GDiGraph

OUTPUT:

  • DiGraph

EXAMPLES:

sage: from stallings_graphs.about_automata import normalize_vertex_names
sage: G = DiGraph([[1,3,7,10,11],[(1,1,1), (1,3,2), (1,11,3), (3,1,2), (3,7,1), (3,7,3), (7,10,2), (7,10,3), (11,10,1)]], format='vertices_and_edges', loops=True, multiedges=True)
sage: GG = normalize_vertex_names(G)
sage: GG.vertices()
[0, 1, 2, 3, 4]
stallings_graphs.about_automata.prepare4visualization_graph(G, alphabet_type='abc', visu_tool='tikz')[source]

Return a DiGraph ready for visualization, with good-looking edge labels.

G is expected to be a DiGraph with numerical edge labels. The value of alphabet_type decides whether these labels will appear as \(a_1,...,a_r\) (alphabet_type='123') or as \(a,b,c,...,z\) (alphabet_type='abc')`. The argument visu_tool prepares the usage of the plot method for graphs (visu_tool='plot') or of Sébastien Labbé’s TikzPicture method (visu_tool='tikz').

INPUT:

  • GDiGraph
  • alphabet_type – string, which can be either 'abc' or '123'
  • visu_tool – string, which can be either 'plot' or 'tikz'

OUTPUT:

  • DiGraph

EXAMPLES:

sage: from stallings_graphs.about_automata import prepare4visualization_graph, bouquet, show_rooted_graph
sage: from stallings_graphs.about_folding import NT_fold
sage: L = [[3,1,-2,-1,3],[1,2,-1,-2,1,2],[1,2,-3,-3,1]]
sage: G = bouquet(L)
sage: GG = NT_fold(G)
sage: GGG = prepare4visualization_graph(GG,alphabet_type='abc',visu_tool='plot')
sage: show_rooted_graph(GGG,0)
Graphics object consisting of 41 graphics primitives
sage: GGG = prepare4visualization_graph(GG,alphabet_type='abc',visu_tool='tikz')
sage: from slabbe import TikzPicture
sage: t = TikzPicture.from_graph(GGG, merge_multiedges=False, edge_labels=True, color_by_label=False, prog='dot')
sage: t.tex()         # not tested
sage: t.pdf()         # not tested
sage: t.png()         # not tested

TESTS:

Dear User, we made sure that production of images works:

sage: _ = t.tex()
sage: _ = t.pdf(view=False)
sage: _ = t.png(view=False)
stallings_graphs.about_automata.pruning(G)[source]

Prune a DiGraph, by iteratively removing degree 1 vertices other than the base vertex (vertex 0).

G is expected to be a DiGraph with numerical edge labels, with vertex set of the form \([0..n]\). The output is another DiGraph, obtained from \(G\) by iteratively removing the degree 1 vertices other than vertex 0 – and relabeling the vertices other than 0 so that the vertex set is of the form \([0..m]\).

INPUT:

  • GDiGraph

OUTPUT:

  • DiGraph

EXAMPLES

sage: from stallings_graphs.about_automata import bouquet, pruning
sage: from stallings_graphs.about_folding import NT_fold
sage: L = [[2,1,-2,2,1,-2], [2,3,1,-3,3,1,-2]]
sage: G = bouquet(L)
sage: GG = NT_fold(G)
sage: GG
Looped multi-digraph on 5 vertices
sage: GGG = pruning(GG)
sage: GGG
Looped multi-digraph on 3 vertices
stallings_graphs.about_automata.relabeling(G, R)[source]

Relabels this DiGraph using the given permutation.

G is expected to a DiGraph with vertices labeled in \([0..n]\). R is expected to be a permutation of \([0..n]\). (No verification is made of that fact.) The output DiGraph is obtained from G by relabeling the vertices of G using the permutation R.

INPUT:

  • GDiGraph
  • R – List

OUTPUT:

  • DiGraph

EXAMPLES:

sage: from stallings_graphs.about_automata import relabeling
sage: G = DiGraph([[0,1,2,3,4],[(0,0,1), (0,1,2), (0,4,3), (1,0,2), (1,2,1), (1,2,3), (2,3,2), (2,3,3), (4,3,1)]], format='vertices_and_edges', loops=True, multiedges=True)
sage: R = [4,1,0,3,2]
sage: GG = relabeling(G,R)
sage: GG
Looped multi-digraph on 5 vertices
stallings_graphs.about_automata.show_rooted_graph(G, base_vertex=0)[source]

Show this rooted DiGraph, emphasizing its base vertex, using the graph.plot method.

G is expected to be a DiGraph with at least one vertex, with a distinguished base_vertex. The graph.plot function is used to show G. The declared base_vertex is colored green, the other vertices are colored white.

INPUT:

  • GDiGraph
  • base_vertex – an object which is a vertex of G

OUTPUT:

  • A graphics object

EXAMPLES

sage: from stallings_graphs.about_automata import prepare4visualization_graph, bouquet, show_rooted_graph
sage: from stallings_graphs.about_folding import NT_fold
sage: L = [[3,1,-2,-1,3],[1,2,-1,-2,1,2],[1,2,-3,-3,1]]
sage: G = bouquet(L)
sage: GG = NT_fold(G)
sage: show_rooted_graph(GG, base_vertex=0)
Graphics object consisting of 41 graphics primitives
stallings_graphs.about_automata.transition_function(digr)[source]

Return a dictionary of the transitions (edges) of this DiGraph.

digr is expected to be a deterministic DiGraph (a ValueError is raised otherwise), with edge labels positive integers. The output dictionary maps each edge label to a list: the image of edge label \(a\) is a list indexed by the vertex set, where the \(v\)-entry is None if one cannot read \(a\) from \(v\), and the result of the \(a\)-transition from \(v\) otherwise.

INPUT:

  • digrDiGraph

OUTPUT:

  • dictionary

EXAMPLES

sage: from stallings_graphs.about_automata import bouquet, transition_function
sage: L = [[3,1,-2,-1,3],[1,2,-1,-2,1,2],[-1,2,-3,-3,1]]
sage: digr = bouquet(L)
sage: transition_function(digr)
{1: [5, 2, None, None, 3, None, None, 6, 9, None, 0, None, None, 0],
 2: [None, None, None, 2, None, 6, None, None, 7, 0, 11, None, None, None],
 3: [1, None, None, None, 0, None, None, None, None, None, None, None, 11, 12]}
stallings_graphs.about_automata.transitions(digr)[source]

Return a dictionary of the transitions (edges) of this DiGraph, organized by edge labels.

digr is expected to be a DiGraph, with labeled edges and with vertex set of the form \([0..n]\). The output dictionary maps each edge label to a list of sets: the image of edge label \(a\) is a list indexed by the vertex set, where the \(v\)-entry is the set of end vertices of \(a\)-labeled edges out of \(v\), or None if that set is empty.

INPUT:

  • digrDiGraph

OUTPUT:

  • dictionary

EXAMPLES:

sage: from stallings_graphs.about_automata import bouquet, transitions
sage: L = [[4,1,1,-4], [-4, -2, -1, 2, -1]]
sage: G = bouquet(L)
sage: transitions(G)
{1: [{7}, {2}, {3}, None, None, None, {5}, None],
 2: [None, None, None, None, None, {4}, {7}, None],
 4: [{1, 3}, None, None, None, {0}, None, None, None]}