Path Semigroups

sage.quivers.path_semigroup.PathSemigroup

The partial semigroup that is given by the directed paths of a quiver, subject to concatenation.

See representation for a definition of this semigroup and of the notion of a path in a quiver.

Note that a partial semigroup here is defined as a set \(G\) with a partial binary operation \(G \times G \to G \cup \{\mbox{None}\}\), which is written infix as a \(*\) sign and satisfies associativity in the following sense: If \(a\), \(b\) and \(c\) are three elements of \(G\), and if one of the products \((a*b)*c\) and \(a*(b*c)\) exists, then so does the other and the two products are equal. A partial semigroup is not required to have a neutral element (and this one usually has no such element).

EXAMPLES:

sage: Q = DiGraph({1:{2:['a','b'], 3:['c']}, 2:{3:['d']}})
sage: S = Q.path_semigroup()
sage: S
Partial semigroup formed by the directed paths of Multi-digraph on 3 vertices
sage: S.variable_names()
('e_1', 'e_2', 'e_3', 'a', 'b', 'c', 'd')
sage: S.gens()
(e_1, e_2, e_3, a, b, c, d)
sage: S.category()
Category of finite enumerated semigroups

In the test suite, we skip the associativity test, as in this example the paths used for testing can’t be concatenated:

sage: TestSuite(S).run(skip=['_test_associativity'])

If there is only a single vertex, the partial semigroup is a monoid. If the underlying quiver has cycles or loops, then the (partial) semigroup only is an infinite enumerated set. This time, there is no need to skip tests:

sage: Q = DiGraph({1:{1:['a', 'b', 'c', 'd']}})
sage: M = Q.path_semigroup()
sage: M
Monoid formed by the directed paths of Looped multi-digraph on 1 vertex
sage: M.category()
Category of infinite enumerated monoids
sage: TestSuite(M).run()