This class implements a number of checks 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.
- See also
- is_obviously_infinite.
|
| IsObviouslyInfinite (IsObviouslyInfinite &&)=delete |
| Deleted.
|
|
| IsObviouslyInfinite (IsObviouslyInfinite const &)=delete |
| Deleted.
|
|
| IsObviouslyInfinite (size_t n) |
| Construct from alphabet size.
|
|
| IsObviouslyInfinite (std::string const &lphbt) |
| Construct from alphabet.
|
|
IsObviouslyInfinite & | add_rules_no_checks (char const *lphbt, typename std::vector< std::string >::const_iterator first, typename std::vector< std::string >::const_iterator last) |
| Add rules from iterators to std::vector of std::string.
|
|
template<typename Char> |
IsObviouslyInfinite & | add_rules_no_checks (std::basic_string< Char > const &lphbt, const_iterator_word_type first, const_iterator_word_type last) |
| Add rules from iterators to word_type.
|
|
template<typename Char> |
IsObviouslyInfinite & | add_rules_no_checks (std::basic_string< Char > const &lphbt, typename std::vector< std::basic_string< Char > >::const_iterator first, typename std::vector< std::basic_string< Char > >::const_iterator last) |
| Add rules from iterators to std::string.
|
|
IsObviouslyInfinite & | add_rules_no_checks (std::string const &lphbt, const_iterator_pair_string first, const_iterator_pair_string last) |
| Add rules from iterators to std::pair of std::string.
|
|
IsObviouslyInfinite & | add_rules_no_checks (word_type const &, const_iterator_word_type first, const_iterator_word_type last) |
| Add rules from iterators to word_type.
|
|
IsObviouslyInfinite & | init (size_t n) |
|
IsObviouslyInfinite & | init (std::string const &lphbt) |
|
IsObviouslyInfinite & | operator= (IsObviouslyInfinite &&)=delete |
| Deleted.
|
|
IsObviouslyInfinite & | operator= (IsObviouslyInfinite const &)=delete |
| Deleted.
|
|
bool | result () const |
| Returns whether or not the finitely presented semigroup or monoid is obviously infinite.
|
|