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}}

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

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

We check that it is a monoid:

sage: M in Monoids()
True

REFERENCES:

AUTHORS:

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

class sage.monoids.trace_monoid.TraceMonoid(M, I, names)#

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 specifing:

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

Element#: alias of TraceMonoidElement

cardinality()#

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

dependence()#

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)]

dependence_graph()#

Return graph of dependence relation.

OUTPUT: dependence graph with generators as vertices

dependence_polynomial(t=None)#

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()
1/(2*t^2 - 4*t + 1)

gen(i=0)#

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

independence()#

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

independence_graph()#

Return the digraph of independence relations.

OUTPUT:

Independence graph with generators as vertices.

ngens()#

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

number_of_words(length)#

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)
48

one()#

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

words(length)#

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]]

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

class sage.monoids.trace_monoid.TraceMonoidElement#

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)

alphabet()#

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}

dependence_graph()#

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()
Digraph on 6 vertices

foata_normal_form()#

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)

hasse_diagram(algorithm='naive')#

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.