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
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 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
DiGraph
to be visualized usingTikzPicture
withalphabet_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.G
is expected to be a foldedDiGraph
(aValueError
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 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
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 ofPartialInjection
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. Inverbose
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. Incertificate
mode: if the subgroups are the same, the output is(True,sigma)
wheresigma
is a conjugating permutation; otherwise the output is(False,None)
.INPUT:
G
–DiGraph
H
–DiGraph
certificate
– booleanverbose
– boolean
OUTPUT: If
certificate
is set toFalse
:- a boolean, if
certificate
is set toFalse
; and ifcertificate
is set toTrue
, a tuple of the form(False,None)
or(True,sigma)
wheresigma
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 classWord
on a symmetric alphabet which is numerical (alphabet_type = '123'
) or consists of letters (alphabet_type = 'abc'
). The optioncheck = True
verifies that this argument is a valid list ofWord
over the givenalphabet_type
. The bouquet in question is aDiGraph
with vertex set of the form \([0..n]\), where every word inlist_of_Words
labels a loop at vertex 0. The edges are labeled by letters from the symmetric alphabet.INPUT:
list_of_Words
– List ofWord
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 aDiGraph
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 theprune
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 theG
(but it will be the same if the base vertex of \(G\) belongs to the cyclic reduction). Iftrace
is 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
–DiGraph
trace
– boolean
OUTPUT:
- a
Digraph
iftrace
is set toFalse
; and a pair(GG, w)
of aDiGraph
and aWord
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 aDiGraph
with vertices \(0,\dots,n-1\), andi
,j
are expected to be vertices of \(G\). Outputs an isomorphicDiGraph
, where the names of the vertices \(i\) and \(j\) have been exchanged.INPUT:
G
–DiGraph
i
– 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.
G1
andG2
are assumed to be of classDiGraph
, with edges labeled by positive integers. Their fibered product is theDiGraph
whose vertex set is the Cartesian product of the sets of vertices ofG1
andG2
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 ifG1
has an \(a\)-labeled edge from \(u_1\) to \(v_1\) andG2
has an \(a\)-labeled edge from \(u_2\) to \(v_2\).INPUT:
G1
–DiGraph
G2
–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 (
None
if it cannot be read).G
is expected to be aDiGraph
whose edges are labeled deterministically and codeterministically (foldedDiGraph
) by a numerical alphabet (typically,G
is a Stallings graph) [not verified],w
is aWord
on a numerical alphabet andqinitial
is a vertex ofG
. If one can readw
fromqinitial
inG
, the output is the vertex reached. If one cannot, the output isNone
. The optiontrace=True
documents the situation ifw
cannot be read inG
: the output is the triple (None
,length_read
,last_vertex_visited
) wherelength_read
is the length of the longest prefixu
ofw
which can be read inG
starting atqinitial
andlast_vertex_visited
is the vertex reached after readingu
.INPUT:
G
–DiGraph
w
–Word
qinitial
– integer (state ofG
)trace
– boolean
OUTPUT:
- integer or
None
iftrace=False
; and iftrace=True
, a triple consisting of three integers orNone
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 aDiGraph
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:
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
DiGraph
is folded (deterministic and co-deterministic).G
is expected to be aDiGraph
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:
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
DiGraph
so they are of the form \([0..n-1]\).G
is expected to be aDiGraph
with vertex set a set of integers (or at least sortable elements). The outputDiGraph
is 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
DiGraph
ready for visualization, with good-looking edge labels.G
is expected to be aDiGraph
with numerical edge labels. The value ofalphabet_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 argumentvisu_tool
prepares the usage of theplot
method for graphs (visu_tool='plot'
) or of Sébastien Labbé’sTikzPicture
method (visu_tool='tikz'
).INPUT:
G
–DiGraph
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 aDiGraph
with 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
DiGraph
using the given permutation.G
is expected to aDiGraph
with vertices labeled in \([0..n]\).R
is expected to be a permutation of \([0..n]\). (No verification is made of that fact.) The outputDiGraph
is obtained fromG
by relabeling the vertices ofG
using the permutationR
.INPUT:
G
–DiGraph
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 thegraph.plot
method.G
is expected to be aDiGraph
with at least one vertex, with a distinguishedbase_vertex
. Thegraph.plot
function is used to showG
. The declaredbase_vertex
is colored green, the other vertices are colored white.INPUT:
G
–DiGraph
base_vertex
– an object which is a vertex ofG
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 deterministicDiGraph
(aValueError
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 isNone
if 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.digr
is 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\), orNone
if 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]}