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(ofalphabet_type'123'or'abc') - extract from a
DiGraphthe list of its transitions (one for each letter labeling an edge) - determine whether a
DiGraphis deterministic and in that case, compute the transition functions (one for each letter labeling an edge) - determine whether a
DiGraphis folded and in that case, compute the corresponding tuple of partial injections (objects of classPartialInjection) - 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
DiGraphto be visualized usingTikzPicturewithalphabet_type'123'or'abc' - show a rooted
DiGraph(usinggraph.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:
- Pascal WEIL (2018-06-09): initial version CNRS, Univ. Bordeaux, LaBRI <pascal.weil@cnrs.fr>
-
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.Gis expected to be a foldedDiGraph(aValueErroris 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 classPartialInjection) induced by edge labels \(1, 2, \dots, r\), respectively.INPUT:
G–DiGraph
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
DiGraphare 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 ofPartialInjectioncoincide, 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. Inverbosemode: 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. Incertificatemode: if the subgroups are the same, the output is(True,sigma)wheresigmais a conjugating permutation; otherwise the output is(False,None).INPUT:
G–DiGraphH–DiGraphcertificate– booleanverbose– boolean
OUTPUT: If
certificateis set toFalse:- a boolean, if
certificateis set toFalse; and ifcertificateis set toTrue, a tuple of the form(False,None)or(True,sigma)wheresigmais 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
Trueoutput 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_Wordsis expected to be a List of objects of classWordon a symmetric alphabet which is numerical (alphabet_type = '123') or consists of letters (alphabet_type = 'abc'). The optioncheck = Trueverifies that this argument is a valid list ofWordover the givenalphabet_type. The bouquet in question is aDiGraphwith vertex set of the form \([0..n]\), where every word inlist_of_Wordslabels a loop at vertex 0. The edges are labeled by letters from the symmetric alphabet.INPUT:
list_of_Words– List ofWordalphabet_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.Gis expected to be aDiGraphwith 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 theprunemethod). 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 theG(but it will be the same if the base vertex of \(G\) belongs to the cyclic reduction). Iftraceis set toTrue, the output includes, in addition to the cyclic reduction ofG, the Word which labels the shortest path from vertex 0 to a vertex that is preserved in the algorithm.INPUT:
G–DiGraphtrace– boolean
OUTPUT:
- a
Digraphiftraceis set toFalse; and a pair(GG, w)of aDiGraphand aWordotherwise.
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.Gis expected to be aDiGraphwith vertices \(0,\dots,n-1\), andi,jare expected to be vertices of \(G\). Outputs an isomorphicDiGraph, where the names of the vertices \(i\) and \(j\) have been exchanged.INPUT:
G–DiGraphi– integerj– 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.
G1andG2are assumed to be of classDiGraph, with edges labeled by positive integers. Their fibered product is theDiGraphwhose vertex set is the Cartesian product of the sets of vertices ofG1andG2and whose edges are as follows: there is an \(a\)-labeled edge from \((u_1,u_2)\) to \((v_1,v_2)\) if and only ifG1has an \(a\)-labeled edge from \(u_1\) to \(v_1\) andG2has an \(a\)-labeled edge from \(u_2\) to \(v_2\).INPUT:
G1–DiGraphG2–DiGraph
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 (
Noneif it cannot be read).Gis expected to be aDiGraphwhose edges are labeled deterministically and codeterministically (foldedDiGraph) by a numerical alphabet (typically,Gis a Stallings graph) [not verified],wis aWordon a numerical alphabet andqinitialis a vertex ofG. If one can readwfromqinitialinG, the output is the vertex reached. If one cannot, the output isNone. The optiontrace=Truedocuments the situation ifwcannot be read inG: the output is the triple (None,length_read,last_vertex_visited) wherelength_readis the length of the longest prefixuofwwhich can be read inGstarting atqinitialandlast_vertex_visitedis the vertex reached after readingu.INPUT:
G–DiGraphw–Wordqinitial– integer (state ofG)trace– boolean
OUTPUT:
- integer or
Noneiftrace=False; and iftrace=True, a triple consisting of three integers orNoneand 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
DiGraphis deterministic.digris expected to be aDiGraphwith 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:
digr–DiGraph
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
DiGraphis folded (deterministic and co-deterministic).Gis expected to be aDiGraphwith 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:
G–DiGraph
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
DiGraphso they are of the form \([0..n-1]\).Gis expected to be aDiGraphwith vertex set a set of integers (or at least sortable elements). The outputDiGraphis isomorphic toG, with vertices labeled \([0..n-1]\), where the new vertex names respect the original order on vertex identifiers.INPUT:
G–DiGraph
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
DiGraphready for visualization, with good-looking edge labels.Gis expected to be aDiGraphwith numerical edge labels. The value ofalphabet_typedecides whether these labels will appear as \(a_1,...,a_r\) (alphabet_type='123') or as \(a,b,c,...,z\) (alphabet_type='abc')`. The argumentvisu_toolprepares the usage of theplotmethod for graphs (visu_tool='plot') or of Sébastien Labbé’sTikzPicturemethod (visu_tool='tikz').INPUT:
G–DiGraphalphabet_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).Gis expected to be aDiGraphwith numerical edge labels, with vertex set of the form \([0..n]\). The output is anotherDiGraph, 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:
G–DiGraph
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
DiGraphusing the given permutation.Gis expected to aDiGraphwith vertices labeled in \([0..n]\).Ris expected to be a permutation of \([0..n]\). (No verification is made of that fact.) The outputDiGraphis obtained fromGby relabeling the vertices ofGusing the permutationR.INPUT:
G–DiGraphR– 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 thegraph.plotmethod.Gis expected to be aDiGraphwith at least one vertex, with a distinguishedbase_vertex. Thegraph.plotfunction is used to showG. The declaredbase_vertexis colored green, the other vertices are colored white.INPUT:
G–DiGraphbase_vertex– an object which is a vertex ofG
OUTPUT:
- A
graphicsobject
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.digris expected to be a deterministicDiGraph(aValueErroris 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 isNoneif one cannot read \(a\) from \(v\), and the result of the \(a\)-transition from \(v\) otherwise.INPUT:
digr–DiGraph
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.digris expected to be aDiGraph, 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\), orNoneif that set is empty.INPUT:
digr–DiGraph
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]}