IsObviouslyInfinite

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:

1. 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.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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.

Public Types
using	const_iterator_pair_string
	Alias for std::vector< std::pair<std::string, std::string>>::const_iterator.
using	const_iterator_string
	Alias for std::vector<std::string>::const_iterator.
using	const_iterator_word_type
	Alias for std::vector<word_type>::const_iterator.

Public Member Functions
	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 (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 (std::string const &lphbt, const_iterator_string first, const_iterator_string last)
	Add rules from iterators to std::string.
IsObviouslyInfinite &	add_rules_no_checks (std::string const &lphbt, const_iterator_word_type first, const_iterator_word_type last)
	Add rules from iterators to word_type.
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.

Member Typedef Documentation

const_iterator_pair_string

using const_iterator_pair_string

Initial value:

 typename std::vector<
        std::pair<std::string, std::string>>::const_iterator

Alias for std::vector< std::pair<std::string, std::string>>::const_iterator.

const_iterator_string

using const_iterator_string

Initial value:

 
        typename std::vector<std::string>::const_iterator

const_iterator_word_type

using const_iterator_word_type

Initial value:

 
        typename std::vector<word_type>::const_iterator

Constructor & Destructor Documentation

IsObviouslyInfinite() [1/2]

IsObviouslyInfinite ( size_t n )

explicit

Constructs an empty IsObviouslyInfinite object representing a finitely presented semigroup or monoid with n generators.

Parameters

n	the number of generators.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

IsObviouslyInfinite() [2/2]

IsObviouslyInfinite ( std::string const & lphbt )

inlineexplicit

Constructs an empty IsObviouslyInfinite object representing a finitely presented semigroup or monoid with alphabet lphbt.

Parameters

lphbt

the alphabet to use.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Member Function Documentation

add_rules_no_checks() [1/4]

IsObviouslyInfinite & add_rules_no_checks	(	std::string const &	lphbt,
		const_iterator_pair_string	first,
		const_iterator_pair_string	last )

This function adds the rules described by the iterators first and last. The rules are translated to word_type objects using the position of each character in the 1st argument lphbt.

Parameters

lphbt	the alphabet to use.
first	iterator pointing at the left-hand-side of the first rule to add.
last	iterator pointing one beyond the right-hand-side of the last rule to add.

Returns

A reference to *this.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Warning

This function does not check its arguments.

add_rules_no_checks() [2/4]

IsObviouslyInfinite & add_rules_no_checks	(	std::string const &	lphbt,
		const_iterator_string	first,
		const_iterator_string	last )

This function adds the rules described by the iterators first and last. The rules are translated to word_type objects using the position of each character in the 1st argument lphbt.

Parameters

lphbt	the alphabet to use.
first	iterator pointing at the left-hand-side of the first rule to add.
last	iterator pointing one beyond the right-hand-side of the last rule to add.

Returns

A reference to *this.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Warning

This function does not check its arguments.

add_rules_no_checks() [3/4]

IsObviouslyInfinite & add_rules_no_checks	(	std::string const &	lphbt,
		const_iterator_word_type	first,
		const_iterator_word_type	last )

This function adds the rules described by the iterators first and last.

Parameters

lphbt	unused (for consistency of interface only).
first	iterator pointing at the left-hand-side of the first rule to add.
last	iterator pointing one beyond the right-hand-side of the last rule to add.

Returns

A reference to *this.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Warning

This function does not check its arguments.

add_rules_no_checks() [4/4]

IsObviouslyInfinite & add_rules_no_checks	(	word_type const &	,
		const_iterator_word_type	first,
		const_iterator_word_type	last )

This function adds the rules described by the iterators first and last.

Parameters

first	iterator pointing at the left-hand-side of the first rule to add.
last	iterator pointing one beyond the right-hand-side of the last rule to add.

Returns

A reference to *this.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Warning

This function does not check its arguments.

init() [1/2]

IsObviouslyInfinite & init

(

size_t

n

)

Re-initialize the object as if it had just been constructed.

Calling this function puts it into the same state that it would have been in if it had just been newly constructed with the same parameter n.

This function exists to allow reuse of the memory allocated within the object.

Parameters

n	the number of generators.

Returns

A reference to *this.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

init() [2/2]

IsObviouslyInfinite & init ( std::string const & lphbt )

inline

Re-initialize the object as if it had just been constructed.

Calling this function puts it into the same state that it would have been in if it had just been newly constructed with the same parameter n.

This function exists to allow reuse of the memory allocated within the object.

Parameters

lphbt

the alphabet to use.

Returns

A reference to *this.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

result()

bool result

(

)

const

This function returns true if the finitely presented semigroup or monoid defined using the alphabet used to construct an IsObviouslyInfinite object, and with relations added to the IsObviouslyInfinite object by add_rules_no_checks, is obviously infinite.

Returns

Whether or not the finitely presented semigroup or monoid is obviously infinite.

---

The documentation for this class was generated from the following file:

• /Users/jdm/libsemigroups/include/libsemigroups/obvinf.hpp