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

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#

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.

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

lex_normal_form()#

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

min_hasse_diagram()#

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

multiplicative_order()#

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

naive_hasse_diagram()#

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

projection(letters)#

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]