Obviously infinite

This page collects the documentation for the functionality in libsemigroups_pybind11 for checking if a finitely presented semigroup or monoid is obviously infinite.

The functions below implement a number of checks for whether or not a finitely presented semigroup or monoid is infinite. These checks are all decidable, and always return an answer within an amount of time that is linear in the size of the input.

These checks are:

For every generator there is at least one side of one relation that consists solely of that generator. If this condition is not met, then there is a generator of infinite order.

The number of occurrences of every generator is not preserved by the relations. Otherwise, it is not possible to use the relations to reduce the number of occurrences of a generator in a word, and so there are infinitely many distinct words.

The number of generators on the left hand side of a relation is not the same as the number of generators on the right hand side for at least one generator. Otherwise the relations preserve the length of any word and so there are infinitely many distinct words.

There are at least as many relations as there are generators. Otherwise we can find a surjective homomorphism onto an infinite subsemigroup of the rationals under addition.

The checks 2., 3. and 4. are a special case of a more general matrix based condition. We construct a matrix whose columns correspond to generators and rows correspond to relations. The (i, j)-th entry is the number of occurrences of the j-th generator in the left hand side of the i-th relation minus the number of occurrences of it on the right hand side. If this matrix has a non-trivial kernel, then we can construct a surjective homomorphism onto an infinite subsemigroup of the rationals under addition. So we check that the matrix is full rank.

The presentation is not that of a free product. To do this we consider a graph whose vertices are generators and an edge connects two generators if they occur on either side of the same relation. If this graph is disconnected then the presentation is a free product and is therefore infinite. Note that we currently do not consider the case where the identity occurs in the presentation.

is_obviously_infinite(*args, **kwargs)

Overloaded function.

is_obviously_infinite(kb: KnuthBendix) → bool

Function for checking if the quotient of a finitely presented semigroup or monoid defined by a KnuthBendix object is obviously infinite or not.

This function returns True if the quotient of the finitely presented semigroup or monoid defined by the KnuthBendix object kb is obviously infinite; False is returned if it is not.

Parameters:: kb (KnuthBendix) – the KnuthBendix instance.
Returns:: Whether or not the congruence defined by a KnuthBendix instance obviously has infinitely many classes.
Return type:: bool

Note

If this function returns False, it is still possible that the quotient defined by the KnuthBendix object kb is infinite.

is_obviously_infinite(c: Congruence) → bool

Function for checking if a congruence obviously has infinite many classes.

This function returns True if the quotient of the finitely presented semigroup or monoid defined by the Congruence object c is obviously infinite; False is returned if it is not.

Parameters:: c (Congruence) – the Congruence instance.
Returns:: Whether or not the congruence obviously has infinitely many classes.
Return type:: bool

Note

If this function returns False, it is still possible that the congruence has infinitely many classes.

is_obviously_infinite(k: Kambites) → bool

Function for checking if the finitely presented semigroup or monoid defined by a Kambites object obviously has infinite many classes.

This function returns True if the finitely presented semigroup or monoid defined by a Kambites object is obviously infinite; False is returned if it is not.

Parameters:: k (Kambites) – the Kambites instance.
Returns:: Whether or not the finitely presented semigroup or monoid defined by a Kambites object is obviously infinite.
Return type:: bool

Note

If this function returns False, it is still possible that finitely presented semigroup or monoid defined by k is infinite.

is_obviously_infinite(p: Presentation) → bool

Function for checking if the finitely presented semigroup or monoid defined by a Presentation object is obviously infinite or not.

This function returns True if the finitely presented semigroup or monoid defined by the Presentation object p is obviously infinite.

Parameters:: p (Presentation) – the presentation.
Returns:: Whether or not the presentation defines an obviously infinite semigroup or monoid.
Return type:: bool
Raises:: LibsemigroupsError – If the presentation p is not valid.

Note

If this function returns False, it is still possible that semigroup or monoid defined by p is infinite.

is_obviously_infinite(tc: ToddCoxeter) → bool

Function for checking if the quotient of a finitely presented semigroup or monoid defined by a ToddCoxeter object is obviously infinite or not.

This function returns True if the quotient of the finitely presented semigroup or monoid defined by the ToddCoxeter object tc is obviously infinite; False is returned if it is not.

Parameters:: tc (ToddCoxeter) – the ToddCoxeter instance.
Returns:: Whether or not the quotient defined by a ToddCoxeter instance is obviously infinite.
Return type:: bool

Note

If this function returns False, it is still possible that the quotient defined by the ToddCoxeter object tc is infinite.