The Konieczny class

The class Konieczny implements Konieczny’s algorithm as described in Konieczny’s article [Kon94]. This algorithm is similar to that of Lallement and McFadden from [LM90]. It differs in being applicable to subsemigroups of a non-regular semigroup, though is essentially the same algorithm for elements which happen to be regular. A Konieczny instance is defined by a generating set, and the main function is Runner.run, which implements Konieczny’s Algorithm. If Runner.run is invoked and Runner.finished returns True, then the size, partial order of \(\mathscr{D}\)-classes, and frames for each \(\mathscr{D}\)-class are known.

See also

Konieczny.DClass and Runner.

Important

The class Konieczny has all the methods of the Runner class but, for boring technical reasons, is not a subclass of Runner. If thing is an instance of Konieczny, then you can use thing as if it were an instance of Runner but isinstance(thing, Runner) will return False.

Contents

`Konieczny`	The class `Konieczny` implements Konieczny's algorithm as described in Konieczny's article [Kon94].
`Konieczny.add_generator`(…)	Add a copy of an element to the generators.
`Konieczny.add_generators`(…)	Add collection of generators from a list.
`Konieczny.contains`(…)	Test membership of an element.
`Konieczny.copy`(…)	Copy a Konieczny.
`Konieczny.current_D_classes`(…)	Returns an iterator yielding the \(\mathscr{D}\)-classes.
`Konieczny.current_number_of_D_classes`(…)	Returns the current number of \(\mathscr{D}\)-classes.
`Konieczny.current_number_of_H_classes`(…)	Returns the current number of \(\mathscr{H}\)-classes.
`Konieczny.current_number_of_L_classes`(…)	Returns the current number of \(\mathscr{L}\)-classes.
`Konieczny.current_number_of_R_classes`(…)	Returns the current number of regular \(\mathscr{R}\)-classes.
`Konieczny.current_number_of_idempotents`(…)	Returns the current number of idempotents.
`Konieczny.current_number_of_regular_D_classes`(…)	Returns the current number of regular \(\mathscr{D}\)-classes
`Konieczny.current_number_of_regular_L_classes`(…)	Returns the current number of regular \(\mathscr{L}\)-classes.
`Konieczny.current_number_of_regular_R_classes`(…)	Returns the current number of regular \(\mathscr{R}\)-classes.
`Konieczny.current_number_of_regular_elements`(…)	Returns the current number of regular elements.
`Konieczny.current_regular_D_classes`(…)	Returns an iterator yielding the so-far enumerated regular \(\mathscr{D}\)-classes of a `Konieczny` object.
`Konieczny.current_size`(…)	Returns the current size.
`Konieczny.degree`(…)	Returns the degree of elements.
`Konieczny.generator`(…)	Returns the generator given by an index.
`Konieczny.generators`(…)	Returns an iterator yielding the generators of a `Konieczny` object.
`Konieczny.init`(…)	Initialize an existing Runner object.
`Konieczny.is_regular_element`(…)	Test regularity of an element.
`Konieczny.number_of_D_classes`(…)	Returns the number of \(\mathscr{D}\)-classes.
`Konieczny.number_of_H_classes`(…)	Returns the number of \(\mathscr{H}\)-classes.
`Konieczny.number_of_L_classes`(…)	Returns the number of \(\mathscr{L}\)-classes.
`Konieczny.number_of_R_classes`(…)	Returns the number of \(\mathscr{R}\)-classes.
`Konieczny.number_of_generators`(…)	Returns the number of generators.
`Konieczny.number_of_idempotents`(…)	Returns the number of idempotents.
`Konieczny.number_of_regular_D_classes`(…)	Returns the number of regular \(\mathscr{D}\)-classes.
`Konieczny.number_of_regular_L_classes`(…)	Returns the number of regular \(\mathscr{L}\)-classes.
`Konieczny.number_of_regular_R_classes`(…)	Returns the number of regular \(\mathscr{R}\)-classes.
`Konieczny.number_of_regular_elements`(…)	Returns the number of regular elements.
`Konieczny.size`(…)	Returns the size.

Full API

class Konieczny

__init__(self: Konieczny, gens: list[Element]) → None

Construct from generators.

This function constructs a Konieczny instance generated by the specified container of generators. There can be duplicate generators and although they do not count as distinct elements, they do count as distinct generators. In other words, the generators are precisely (a copy of) gens in the same order they occur in gens.

Parameters:

gens (list[Element]) – the generators represented by this.

Raises:

LibsemigroupsError – if gens is empty.
LibsemigroupsError – if the items in gens do not all have the same degree.

D_class_of_element(self: Konieczny, x: Element) → Konieczny.DClass

Returns the \(\mathscr{D}\)-class containing an element.

Parameters:: x (Element) – a possible element.
Returns:: The Konieczny.DClass containing x.
Return type:: Konieczny.DClass
Raises:: LibsemigroupsError – if x does not belong to self.

D_classes(self: Konieczny) → collections.abc.Iterator[Konieczny.DClass]

Returns an iterator yielding the \(\mathscr{D}\)-classes of a Konieczny object. This function triggers a full enumeration.

Returns:: An iterator yielding \(\mathscr{D}\)-classes.
Return type:: collections.abc.Iterator[Konieczny.DClass]

add_generator(self: Konieczny, gen: Element) → Konieczny

Add a copy of an element to the generators.

It is possible, if perhaps not desirable, to add the same generator multiple times.

Parameters:

gen (Element) – the generator to add.

Returns:

self.

Return type:

Konieczny

Raises:

LibsemigroupsError – if the degree of x is incompatible with the existing degree.
LibsemigroupsError – if started returns True.

add_generators(self: Konieczny, coll: list[Element]) → Konieczny

Add collection of generators from a list.

See Konieczny.add_generator for a detailed description.

Parameters:

coll (list[Element]) – the collection of generators to add.

Returns:

self.

Return type:

Konieczny

Raises:

LibsemigroupsError – the degree of any item in coll is incompatible with the existing degree (if any).
LibsemigroupsError – started returns True.

contains(self: Konieczny, x: Element) → bool

Test membership of an element.

Returns True if x belongs to self and False if it does not.

Parameters:: x (Element) – a possible element.
Returns:: Whether or not x belongs to the semigroup represented by a Konieczny object.
Return type:: bool

copy(self: Konieczny) → Konieczny

Copy a Konieczny.

Returns:: A copy of the argument.
Return type:: Konieczny

current_D_classes(self: Konieczny) → collections.abc.Iterator[Konieczny.DClass]

Returns an iterator yielding the \(\mathscr{D}\)-classes.

This function does not trigger any enumeration; the iterator returned may be invalidated by any call to a non-const member function of the Konieczny class.

Returns:: An iterator.
Return type:: collections.abc.Iterator[Konieczny.DClass]

current_number_of_D_classes(self: Konieczny) → int

Returns the current number of \(\mathscr{D}\)-classes.

Returns:: The number of \(\mathscr{D}\)-classes so far enumerated.
Return type:: int

current_number_of_H_classes(self: Konieczny) → int

Returns the current number of \(\mathscr{H}\)-classes.

Returns:: The number of \(\mathscr{H}\)-classes so far enumerated.
Return type:: int

current_number_of_L_classes(self: Konieczny) → int

Returns the current number of \(\mathscr{L}\)-classes.

Returns:: The number of \(\mathscr{L}\)-classes so far enumerated.
Return type:: int

current_number_of_R_classes(self: Konieczny) → int

Returns the current number of regular \(\mathscr{R}\)-classes.

Returns:: The number of \(\mathscr{L}\)-classes so far enumerated.
Return type:: int

current_number_of_idempotents(self: Konieczny) → int

Returns the current number of idempotents.

Returns:: The number of idempotents so far enumerated.
Return type:: int

current_number_of_regular_D_classes(self: Konieczny) → int

Returns the current number of regular \(\mathscr{D}\)-classes

Returns:: The number of regular \(\mathscr{D}\)-classes so far enumerated.
Return type:: int

current_number_of_regular_L_classes(self: Konieczny) → int

Returns the current number of regular \(\mathscr{L}\)-classes.

Returns:: The number of regular \(\mathscr{L}\)-classes so far enumerated.
Return type:: int

current_number_of_regular_R_classes(self: Konieczny) → int

Returns the current number of regular \(\mathscr{R}\)-classes.

Returns:: The number of regular \(\mathscr{R}\)-classes so far enumerated.
Return type:: int

current_number_of_regular_elements(self: Konieczny) → int

Returns the current number of regular elements.

Returns:: The number of regular elements so far enumerated.
Return type:: int

current_regular_D_classes(self: Konieczny) → collections.abc.Iterator[Konieczny.DClass]

Returns an iterator yielding the so-far enumerated regular \(\mathscr{D}\)-classes of a Konieczny object. This function does not trigger any enumeration; the iterator returned may be invalidated by any call to a non-const member function of the Konieczny class.

Returns:: An iterator yielding regular \(\mathscr{D}\)-classes.
Return type:: collections.abc.Iterator[Konieczny.DClass]

current_size(self: Konieczny) → int

Returns the current size.

Returns:: The number of elements so far enumerated.
Return type:: int

See also

Konieczny.size.

degree(self: Konieczny) → int

Returns the degree of elements. All elements of a Konieczny must have the same degree; this function returns that degree.

Returns:: The degree of any (and all) elements.
Return type:: int

generator(self: Konieczny, pos: int) → Element

Returns the generator given by an index.

This function returns the generator of self with index pos.

Parameters:: pos (int) – the index of the generator.
Returns:: The generator with given index.
Return type:: Element
Raises:: LibsemigroupsError – if the value of pos is greater than number_of_generators().
Complexity:: Constant.

generators(self: Konieczny) → collections.abc.Iterator[Konieczny.DClass]

Returns an iterator yielding the generators of a Konieczny object. This function does not trigger any enumeration; the iterator returned may be invalidated by any call to a non-const member function of the Konieczny class.

Returns:: An iterator yielding the generators.
Return type:: collections.abc.Iterator[Konieczny.DClass]

init(self: Runner) → Runner

Initialize an existing Runner object.

This function puts a Runner object back into the same state as if it had been newly default constructed.

Returns:: self.
Return type:: Runner

See also

Runner()

is_regular_element(self: Konieczny, x: Element) → bool

Test regularity of an element.

This function returns True if x is a regular element and False if it is not.

Parameters:: x (Element) – a possible element.
Returns:: Whether or not x belongs to self.
Return type:: bool

number_of_D_classes(self: Konieczny) → int

Returns the number of \(\mathscr{D}\)-classes.

Returns:: The number of \(\mathscr{D}\)-classes.
Return type:: int

number_of_H_classes(self: Konieczny) → int

Returns the number of \(\mathscr{H}\)-classes.

Returns:: The number of \(\mathscr{H}\)-classes.
Return type:: int

number_of_L_classes(self: Konieczny) → int

Returns the number of \(\mathscr{L}\)-classes.

Returns:: The number of \(\mathscr{L}\)-classes.
Return type:: int

number_of_R_classes(self: Konieczny) → int

Returns the number of \(\mathscr{R}\)-classes.

Returns:: The number of \(\mathscr{R}\)-classes.
Return type:: int

number_of_generators(self: Konieczny) → int

Returns the number of generators.

This function returns the number of generators given to self. Note that there may be duplicate generators, and so self may have more generators than unique generators.

Returns:: The number of generators.
Return type:: int

number_of_idempotents(self: Konieczny) → int

Returns the number of idempotents.

Returns:: The number of idempotents.
Return type:: int

number_of_regular_D_classes(self: Konieczny) → int

Returns the number of regular \(\mathscr{D}\)-classes.

Returns:: The number of regular \(\mathscr{D}\)-classes.
Return type:: int

number_of_regular_L_classes(self: Konieczny) → int

Returns the number of regular \(\mathscr{L}\)-classes.

Returns:: The number of regular \(\mathscr{L}\)-classes.
Return type:: int

number_of_regular_R_classes(self: Konieczny) → int

Returns the number of regular \(\mathscr{R}\)-classes.

Returns:: The number of regular \(\mathscr{R}\)-classes.
Return type:: int

number_of_regular_elements(self: Konieczny) → int

Returns the number of regular elements.

Returns:: The number of regular elements.
Return type:: int

size(self: Konieczny) → int

Returns the size.

This function triggers a full enumeration.

Returns:: The size.
Return type:: int

See also

current_size.