Module of trace monoids (free partially commutative monoids).

EXAMPLES:

We first create a trace monoid:

sage: from sage.monoids.trace_monoid import TraceMonoid
sage: M.<a,b,c> = TraceMonoid(I=(('a','c'), ('c','a'))); M
Trace monoid on 3 generators ([a], [b], [c]) with independence relation {{a, c}}

>>> from sage.all import *
>>> from sage.monoids.trace_monoid import TraceMonoid
>>> M = TraceMonoid(I=(('a','c'), ('c','a')), names=('a', 'b', 'c',)); (a, b, c,) = M._first_ngens(3); M
Trace monoid on 3 generators ([a], [b], [c]) with independence relation {{a, c}}

Different elements can be equal because of the partially commutative multiplication:

sage: c * a * b == a * c * b
True

>>> from sage.all import *
>>> c * a * b == a * c * b
True

We check that it is a monoid:

sage: M in Monoids()
True

>>> from sage.all import *
>>> M in Monoids()
True

REFERENCES:

AUTHORS:

  • Pavlo Tokariev (2019-05-31): initial version

class sage.monoids.trace_monoid.TraceMonoid(M, I, names)[source]

Bases: UniqueRepresentation, Monoid_class

Return a free partially commuting monoid (trace monoid) on \(n\) generators over independence relation \(I\).

We construct a trace monoid by specifying:

  • a free monoid and independence relation

  • or generator names and independence relation, FreeMonoid is constructed automatically then.

INPUT:

  • M – a free monoid

  • I – commutation relation between generators (or their names if the names are given)

  • names – names of generators

EXAMPLES:

sage: from sage.monoids.trace_monoid import TraceMonoid
sage: F = TraceMonoid(names=('a', 'b', 'c'), I={('a','c'), ('c','a')}); F
Trace monoid on 3 generators ([a], [b], [c]) with independence relation {{a, c}}
sage: x = F.gens()
sage: x[0]*x[1]**5 * (x[0]*x[2])
[a*b^5*a*c]

sage: from sage.monoids.trace_monoid import TraceMonoid
sage: M.<a,b,c> = TraceMonoid(I=(('a','c'), ('c','a')))
sage: latex(M)
\langle a, b, c \mid ac=ca \rangle

>>> from sage.all import *
>>> from sage.monoids.trace_monoid import TraceMonoid
>>> F = TraceMonoid(names=('a', 'b', 'c'), I={('a','c'), ('c','a')}); F
Trace monoid on 3 generators ([a], [b], [c]) with independence relation {{a, c}}
>>> x = F.gens()
>>> x[Integer(0)]*x[Integer(1)]**Integer(5) * (x[Integer(0)]*x[Integer(2)])
[a*b^5*a*c]

>>> from sage.monoids.trace_monoid import TraceMonoid
>>> M = TraceMonoid(I=(('a','c'), ('c','a')), names=('a', 'b', 'c',)); (a, b, c,) = M._first_ngens(3)
>>> latex(M)
\langle a, b, c \mid ac=ca \rangle
Element[source]

alias of TraceMonoidElement

cardinality()[source]

Return the cardinality of self, which is infinite except for the trivial monoid.

EXAMPLES:

sage: from sage.monoids.trace_monoid import TraceMonoid
sage: M.<a,b,c> = TraceMonoid(I=(('a','c'), ('c','a')))
sage: M.cardinality()
+Infinity

>>> from sage.all import *
>>> from sage.monoids.trace_monoid import TraceMonoid
>>> M = TraceMonoid(I=(('a','c'), ('c','a')), names=('a', 'b', 'c',)); (a, b, c,) = M._first_ngens(3)
>>> M.cardinality()
+Infinity
dependence()[source]

Return dependence relation over the monoid.

OUTPUT: set of non-commuting generator pairs

EXAMPLES:

sage: from sage.monoids.trace_monoid import TraceMonoid
sage: M.<a,b,c> = TraceMonoid(I=(('a','c'), ('c','a')))
sage: sorted(M.dependence())
[(a, a), (a, b), (b, a), (b, b), (b, c), (c, b), (c, c)]

>>> from sage.all import *
>>> from sage.monoids.trace_monoid import TraceMonoid
>>> M = TraceMonoid(I=(('a','c'), ('c','a')), names=('a', 'b', 'c',)); (a, b, c,) = M._first_ngens(3)
>>> sorted(M.dependence())
[(a, a), (a, b), (b, a), (b, b), (b, c), (c, b), (c, c)]
dependence_graph()[source]

Return graph of dependence relation.

OUTPUT: dependence graph with generators as vertices

dependence_polynomial(t=None)[source]

Return dependence polynomial.

The polynomial is defined as follows: \(\sum{i}{(-1)^i c_i t^i}\), where \(c_i\) equals to number of full subgraphs of size \(i\) in the independence graph.

OUTPUT: a rational function in t with coefficients in the integer ring

EXAMPLES:

sage: from sage.monoids.trace_monoid import TraceMonoid
sage: I = (('a','d'), ('d','a'), ('b','c'), ('c','b'))
sage: M.<a,b,c,d> = TraceMonoid(I=I)
sage: M.dependence_polynomial()                                             # needs sage.graphs
1/(2*t^2 - 4*t + 1)

>>> from sage.all import *
>>> from sage.monoids.trace_monoid import TraceMonoid
>>> I = (('a','d'), ('d','a'), ('b','c'), ('c','b'))
>>> M = TraceMonoid(I=I, names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = M._first_ngens(4)
>>> M.dependence_polynomial()                                             # needs sage.graphs
1/(2*t^2 - 4*t + 1)
gen(i=0)[source]

Return the \(i\)-th generator of the monoid.

INPUT:

  • i – integer (default: 0)

EXAMPLES:

sage: from sage.monoids.trace_monoid import TraceMonoid
sage: M.<a,b,c> = TraceMonoid(I=(('a','c'), ('c','a')))
sage: M.gen(1)
[b]
sage: M.gen(4)
Traceback (most recent call last):
...
IndexError: argument i (= 4) must be between 0 and 2

>>> from sage.all import *
>>> from sage.monoids.trace_monoid import TraceMonoid
>>> M = TraceMonoid(I=(('a','c'), ('c','a')), names=('a', 'b', 'c',)); (a, b, c,) = M._first_ngens(3)
>>> M.gen(Integer(1))
[b]
>>> M.gen(Integer(4))
Traceback (most recent call last):
...
IndexError: argument i (= 4) must be between 0 and 2
independence()[source]

Return independence relation over the monoid.

OUTPUT: set of commuting generator pairs

EXAMPLES:

sage: from sage.monoids.trace_monoid import TraceMonoid
sage: F.<a,b,c> = FreeMonoid()
sage: I = frozenset(((a,c), (c,a)))
sage: M.<ac,bc,cc> = TraceMonoid(F, I=I)
sage: M.independence() == frozenset([frozenset([a,c])])
True

>>> from sage.all import *
>>> from sage.monoids.trace_monoid import TraceMonoid
>>> F = FreeMonoid(names=('a', 'b', 'c',)); (a, b, c,) = F._first_ngens(3)
>>> I = frozenset(((a,c), (c,a)))
>>> M = TraceMonoid(F, I=I, names=('ac', 'bc', 'cc',)); (ac, bc, cc,) = M._first_ngens(3)
>>> M.independence() == frozenset([frozenset([a,c])])
True
independence_graph()[source]

Return the digraph of independence relations.

OUTPUT: independence graph with generators as vertices

ngens()[source]

Return the number of generators of self.

EXAMPLES:

sage: from sage.monoids.trace_monoid import TraceMonoid
sage: M.<a,b,c> = TraceMonoid(I=(('a','c'), ('c','a')))
sage: M.ngens()
3

>>> from sage.all import *
>>> from sage.monoids.trace_monoid import TraceMonoid
>>> M = TraceMonoid(I=(('a','c'), ('c','a')), names=('a', 'b', 'c',)); (a, b, c,) = M._first_ngens(3)
>>> M.ngens()
3
number_of_words(length)[source]

Return number of unique words of defined length.

INPUT:

  • length – integer; defines size of words what number should be computed

OUTPUT: words number as integer

EXAMPLES:

Get number of words of size 3

sage: from sage.monoids.trace_monoid import TraceMonoid
sage: I = (('a','d'), ('d','a'), ('b','c'), ('c','b'))
sage: M.<a,b,c,d> = TraceMonoid(I=I)
sage: M.number_of_words(3)                                                  # needs sage.graphs
48

>>> from sage.all import *
>>> from sage.monoids.trace_monoid import TraceMonoid
>>> I = (('a','d'), ('d','a'), ('b','c'), ('c','b'))
>>> M = TraceMonoid(I=I, names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = M._first_ngens(4)
>>> M.number_of_words(Integer(3))                                                  # needs sage.graphs
48
one()[source]

Return the neutral element of self.

EXAMPLES:

sage: from sage.monoids.trace_monoid import TraceMonoid
sage: M.<a,b,c> = TraceMonoid(I=(('a','c'), ('c','a')))
sage: M.one()
1

>>> from sage.all import *
>>> from sage.monoids.trace_monoid import TraceMonoid
>>> M = TraceMonoid(I=(('a','c'), ('c','a')), names=('a', 'b', 'c',)); (a, b, c,) = M._first_ngens(3)
>>> M.one()
1
words(length)[source]

Return all lexicographic forms of defined length.

INPUT:

  • length – integer; defines size of words

OUTPUT: set of traces of size length

EXAMPLES:

All words of size 2:

sage: from sage.monoids.trace_monoid import TraceMonoid
sage: I = (('a','d'), ('d','a'), ('b','c'), ('c','b'))
sage: M.<a,b,c,d> = TraceMonoid(I=I)
sage: sorted(M.words(2))
[[a^2], [a*b], [a*c], [a*d], [b*a], [b^2], [b*c],
 [b*d], [c*a], [c^2], [c*d], [d*b], [d*c], [d^2]]

>>> from sage.all import *
>>> from sage.monoids.trace_monoid import TraceMonoid
>>> I = (('a','d'), ('d','a'), ('b','c'), ('c','b'))
>>> M = TraceMonoid(I=I, names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = M._first_ngens(4)
>>> sorted(M.words(Integer(2)))
[[a^2], [a*b], [a*c], [a*d], [b*a], [b^2], [b*c],
 [b*d], [c*a], [c^2], [c*d], [d*b], [d*c], [d^2]]

Get number of words of size 3:

sage: from sage.monoids.trace_monoid import TraceMonoid
sage: I = (('a','d'), ('d','a'), ('b','c'), ('c','b'))
sage: M.<a,b,c,d> = TraceMonoid(I=I)
sage: len(M.words(3))
48

>>> from sage.all import *
>>> from sage.monoids.trace_monoid import TraceMonoid
>>> I = (('a','d'), ('d','a'), ('b','c'), ('c','b'))
>>> M = TraceMonoid(I=I, names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = M._first_ngens(4)
>>> len(M.words(Integer(3)))
48
class sage.monoids.trace_monoid.TraceMonoidElement[source]

Bases: ElementWrapper, MonoidElement

Element of a trace monoid, also known as a trace.

Elements of trace monoid is actually a equivalence classes of related free monoid over some equivalence relation that in the case is presented as independence relation.

Representative

We transform each trace to its lexicographic form for the representative in the ambient free monoid. This is also used for comparisons.

EXAMPLES:

sage: from sage.monoids.trace_monoid import TraceMonoid
sage: I = (('a','d'), ('d','a'), ('b','c'), ('c','b'))
sage: M.<a,b,c,d> = TraceMonoid(I=I)
sage: x = b * a * d * a * c * b
sage: x^3
[b*a^2*d*b^2*c*a^2*d*b^2*c*a^2*d*b*c]
sage: x^0
1
sage: x.lex_normal_form()
b*a^2*d*b*c
sage: x.foata_normal_form()
(b, a*d, a, b*c)

>>> from sage.all import *
>>> from sage.monoids.trace_monoid import TraceMonoid
>>> I = (('a','d'), ('d','a'), ('b','c'), ('c','b'))
>>> M = TraceMonoid(I=I, names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = M._first_ngens(4)
>>> x = b * a * d * a * c * b
>>> x**Integer(3)
[b*a^2*d*b^2*c*a^2*d*b^2*c*a^2*d*b*c]
>>> x**Integer(0)
1
>>> x.lex_normal_form()
b*a^2*d*b*c
>>> x.foata_normal_form()
(b, a*d, a, b*c)
alphabet()[source]

Return alphabet of self.

OUTPUT: a set of free monoid generators

EXAMPLES:

sage: from sage.monoids.trace_monoid import TraceMonoid
sage: I = (('a','d'), ('d','a'), ('b','c'), ('c','b'))
sage: M.<a,b,c,d> = TraceMonoid(I=I)
sage: x = b*a*d*a*c*b
sage: x.alphabet()
{b, a, d, c}

>>> from sage.all import *
>>> from sage.monoids.trace_monoid import TraceMonoid
>>> I = (('a','d'), ('d','a'), ('b','c'), ('c','b'))
>>> M = TraceMonoid(I=I, names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = M._first_ngens(4)
>>> x = b*a*d*a*c*b
>>> x.alphabet()
{b, a, d, c}
dependence_graph()[source]

Return dependence graph of the trace.

It is a directed graph where all dependent (non-commutative) generators are connected by edges which direction depend on the generator position in the trace.

OUTPUT: directed graph of generator indexes

EXAMPLES:

sage: from sage.monoids.trace_monoid import TraceMonoid
sage: I = (('a','d'), ('d','a'), ('b','c'), ('c','b'))
sage: M.<a,b,c,d> = TraceMonoid(I=I)
sage: x = b * a * d * a * c * b
sage: x.dependence_graph()                                                  # needs sage.graphs
Digraph on 6 vertices

>>> from sage.all import *
>>> from sage.monoids.trace_monoid import TraceMonoid
>>> I = (('a','d'), ('d','a'), ('b','c'), ('c','b'))
>>> M = TraceMonoid(I=I, names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = M._first_ngens(4)
>>> x = b * a * d * a * c * b
>>> x.dependence_graph()                                                  # needs sage.graphs
Digraph on 6 vertices
foata_normal_form()[source]

Return the Foata normal form of self.

OUTPUT: tuple of free monoid elements

EXAMPLES:

sage: from sage.monoids.trace_monoid import TraceMonoid
sage: I = (('a','d'), ('d','a'), ('b','c'), ('c','b'))
sage: M.<a,b,c,d> = TraceMonoid(I=I)
sage: x = b * a * d * a * c * b
sage: x.foata_normal_form()
(b, a*d, a, b*c)

>>> from sage.all import *
>>> from sage.monoids.trace_monoid import TraceMonoid
>>> I = (('a','d'), ('d','a'), ('b','c'), ('c','b'))
>>> M = TraceMonoid(I=I, names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = M._first_ngens(4)
>>> x = b * a * d * a * c * b
>>> x.foata_normal_form()
(b, a*d, a, b*c)
hasse_diagram(algorithm='naive')[source]

Return Hasse diagram of the trace.

Hasse diagram is a dependence graph without transitive edges.

INPUT:

  • algorithm – string (default: 'naive'); defines algorithm that will be used to compute Hasse diagram; there are two variants: 'naive' and 'min'.

OUTPUT: directed graph of generator indexes

See also

naive_hasse_digram(), min_hasse_diagram().

EXAMPLES:

sage: from sage.monoids.trace_monoid import TraceMonoid
sage: I = (('a','d'), ('d','a'), ('b','c'), ('c','b'))
sage: M.<a,b,c,d> = TraceMonoid(I=I)
sage: x = b * a * d * a * c * b
sage: x.hasse_diagram()                                                     # needs sage.graphs
Digraph on 6 vertices

>>> from sage.all import *
>>> from sage.monoids.trace_monoid import TraceMonoid
>>> I = (('a','d'), ('d','a'), ('b','c'), ('c','b'))
>>> M = TraceMonoid(I=I, names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = M._first_ngens(4)
>>> x = b * a * d * a * c * b
>>> x.hasse_diagram()                                                     # needs sage.graphs
Digraph on 6 vertices
lex_normal_form()[source]

Return the lexicographic normal form of self.

OUTPUT: a free monoid element

EXAMPLES:

sage: from sage.monoids.trace_monoid import TraceMonoid
sage: I = (('a','d'), ('d','a'), ('b','c'), ('c','b'))
sage: M.<a,b,c,d> = TraceMonoid(I=I)
sage: (a*b).lex_normal_form()
a*b
sage: (b*a).lex_normal_form()
b*a
sage: (d*a).lex_normal_form()
a*d

>>> from sage.all import *
>>> from sage.monoids.trace_monoid import TraceMonoid
>>> I = (('a','d'), ('d','a'), ('b','c'), ('c','b'))
>>> M = TraceMonoid(I=I, names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = M._first_ngens(4)
>>> (a*b).lex_normal_form()
a*b
>>> (b*a).lex_normal_form()
b*a
>>> (d*a).lex_normal_form()
a*d
min_hasse_diagram()[source]

Return Hasse diagram of the trace.

OUTPUT: directed graph of generator indexes

See also

hasse_digram(), naive_hasse_diagram().

EXAMPLES:

sage: from sage.monoids.trace_monoid import TraceMonoid
sage: I = (('a','d'), ('d','a'), ('b','c'), ('c','b'))
sage: M.<a,b,c,d> = TraceMonoid(I=I)
sage: x = b * a * d * a * c * b
sage: x.min_hasse_diagram()                                                 # needs sage.graphs
Digraph on 6 vertices

>>> from sage.all import *
>>> from sage.monoids.trace_monoid import TraceMonoid
>>> I = (('a','d'), ('d','a'), ('b','c'), ('c','b'))
>>> M = TraceMonoid(I=I, names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = M._first_ngens(4)
>>> x = b * a * d * a * c * b
>>> x.min_hasse_diagram()                                                 # needs sage.graphs
Digraph on 6 vertices
multiplicative_order()[source]

Return the multiplicative order of self, which is \(\infty\) for any element not the identity.

EXAMPLES:

sage: from sage.monoids.trace_monoid import TraceMonoid
sage: I = (('a','d'), ('d','a'), ('b','c'), ('c','b'))
sage: M.<a,b,c,d> = TraceMonoid(I=I)
sage: a.multiplicative_order()
+Infinity
sage: M.one().multiplicative_order()
1

>>> from sage.all import *
>>> from sage.monoids.trace_monoid import TraceMonoid
>>> I = (('a','d'), ('d','a'), ('b','c'), ('c','b'))
>>> M = TraceMonoid(I=I, names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = M._first_ngens(4)
>>> a.multiplicative_order()
+Infinity
>>> M.one().multiplicative_order()
1
naive_hasse_diagram()[source]

Return Hasse diagram of self.

ALGORITHM:

In loop check for every two pair of edges if they have common vertex, remove their transitive edge.

OUTPUT: directed graph of generator indexes

See also

hasse_digram(), min_hasse_diagram().

EXAMPLES:

sage: from sage.monoids.trace_monoid import TraceMonoid
sage: I = (('a','d'), ('d','a'), ('b','c'), ('c','b'))
sage: M.<a,b,c,d> = TraceMonoid(I=I)
sage: x = b * a * d * a * c * b
sage: x.naive_hasse_diagram()                                               # needs sage.graphs
Digraph on 6 vertices

>>> from sage.all import *
>>> from sage.monoids.trace_monoid import TraceMonoid
>>> I = (('a','d'), ('d','a'), ('b','c'), ('c','b'))
>>> M = TraceMonoid(I=I, names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = M._first_ngens(4)
>>> x = b * a * d * a * c * b
>>> x.naive_hasse_diagram()                                               # needs sage.graphs
Digraph on 6 vertices
projection(letters)[source]

Return a trace that formed from self by erasing letters.

INPUT:

  • letters – set of generators; defines set of letters that will be used to filter the trace

OUTPUT: a trace

EXAMPLES:

sage: from sage.monoids.trace_monoid import TraceMonoid
sage: F.<a,b,c,d> = FreeMonoid()
sage: I = ((a,d), (d,a), (b,c), (c,b))
sage: M.<ac,bc,cc,dc> = TraceMonoid(F, I=I)
sage: x = M(b*a*d*a*c*b)
sage: x.projection({a,b})
[b*a^2*b]
sage: x.projection({b,d,c})
[b*d*b*c]

>>> from sage.all import *
>>> from sage.monoids.trace_monoid import TraceMonoid
>>> F = FreeMonoid(names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = F._first_ngens(4)
>>> I = ((a,d), (d,a), (b,c), (c,b))
>>> M = TraceMonoid(F, I=I, names=('ac', 'bc', 'cc', 'dc',)); (ac, bc, cc, dc,) = M._first_ngens(4)
>>> x = M(b*a*d*a*c*b)
>>> x.projection({a,b})
[b*a^2*b]
>>> x.projection({b,d,c})
[b*d*b*c]