FpSemigroup

This is a class for representing finitely presented semigroups and monoids.

On this page we describe the functionality relating to the FpSemigroup class. This class can be used for computing a finitely presented semigroup or monoid by running every applicable algorithm from libsemigroups (and possibly some variants of the same algorithm) in parallel. This class is provided for convenience, at present it is not very customisable, and lacks some of the fine grained control offered by the classes implementing individual algorithms, such as ToddCoxeter and KnuthBendix.

>>> from libsemigroups_pybind11 import FpSemigroup
>>> S = FpSemigroup()
>>> S.set_alphabet(3)
>>> S.set_identity(0)
>>> S.add_rule([1, 2], [0])
>>> S.is_obviously_infinite()
True
class FpSemigroup(*args, **kwargs)

Overloaded function.

  1. __init__(self: _libsemigroups_pybind11.FpSemigroup) -> None

  2. __init__(self: _libsemigroups_pybind11.FpSemigroup, arg0: libsemigroups::FroidurePinBase) -> None

  3. __init__(self: _libsemigroups_pybind11.FpSemigroup, arg0: _libsemigroups_pybind11.FpSemigroup) -> None

add_rule(*args, **kwargs)

Overloaded function.

  1. add_rule(self: _libsemigroups_pybind11.FpSemigroup, rel: Tuple[List[int], List[int]]) -> None

    Add a rule.

    Parameters

    rel (Tuple[List[int], List[int]]) - the rule being added.

    Returns

    (None)

  2. add_rule(self: _libsemigroups_pybind11.FpSemigroup, rel: Tuple[str, str]) -> None

    Add a rule.

    Parameters

    rel (Tuple[str, str]) - the rule being added.

    Returns

    (None)

  3. add_rule(self: _libsemigroups_pybind11.FpSemigroup, u: str, v: str) -> None

    Add a rule.

    Parameters

    • u (str) - the left-hand side of the rule being added.

    • v (str) - the right-hand side of the rule being added.

    Returns

    (None)

  4. add_rule(self: _libsemigroups_pybind11.FpSemigroup, u: List[int], v: List[int]) -> None

    Add a rule.

    Parameters

    • u (List[int]) - the left-hand side of the rule being added.

    • v (List[int]) - the right-hand side of the rule being added.

    Returns

    (None)

add_rules(*args, **kwargs)

Overloaded function.

  1. add_rules(self: _libsemigroups_pybind11.FpSemigroup, S: libsemigroups::FroidurePinBase) -> None

    Add the rules of a finite presentation for S to this.

    Parameters

    S (FroidurePin) - a FroidurePin object representing a semigroup.

    Returns

    (None)

  2. add_rules(self: _libsemigroups_pybind11.FpSemigroup, rels: List[Tuple[str, str]]) -> None

    Add the rules in the given list to the finitely presented semigroup.

    Parameters

    rels (List[Tuple[str, str]]) - the rules to add.

    Returns

    (None)

alphabet(*args, **kwargs)

Overloaded function.

  1. alphabet(self: _libsemigroups_pybind11.FpSemigroup) -> str

    Returns the alphabet of the finitely presented semigroup represented.

    Returns

    A string.

  2. alphabet(self: _libsemigroups_pybind11.FpSemigroup, i: int) -> str

    Returns the i-th letter of the alphabet of the finitely presented semigroup.

    Parameters

    i (int) - the index of the letter.

    Returns

    A string.

char_to_uint(self: _libsemigroups_pybind11.FpSemigroup, a: str) → int

Convert a string of length 1 to an int representing the same generator of the finitely presented semigroup.

Parameters

a (str) -- the string to convert.

Returns

An int.

dead(self: libsemigroups::Runner) → bool

Check if the algorithm was killed.

Returns

A bool.

equal_to(*args, **kwargs)

Overloaded function.

  1. equal_to(self: _libsemigroups_pybind11.FpSemigroup, u: str, v: str) -> bool

    Check if two words represent the same element.

    Parameters

    • u (str) - the first word, must be a string over alphabet().

    • v (str) - the second word, must be a string over alphabet().

    Returns

    True if the strings u and v represent the same element of the finitely presented semigroup, and False otherwise.

  2. equal_to(self: _libsemigroups_pybind11.FpSemigroup, u: List[int], v: List[int]) -> bool

    Check if two words represent the same element.

    Parameters

    • u (List[int]) - the first word.

    • v (List[int]) - the second word.

    Returns

    True if the words u and v represent the same element of the finitely presented semigroup, and False otherwise.

finished(self: _libsemigroups_pybind11.FpSemigroup) → bool

Check if the algorithm has been run to completion or not.

Returns

A bool.

froidure_pin(self: _libsemigroups_pybind11.FpSemigroup) → libsemigroups::FroidurePinBase

Returns a FroidurePin instance isomorphic to the finitely presented semigroup.

Returns

A FroidurePin instance.

has_froidure_pin(self: _libsemigroups_pybind11.FpSemigroup) → bool

Returns True if a FroidurePin instance isomorphic to the finitely presented semigroup has already been computed, and False if not.

Returns

A bool.

has_knuth_bendix(self: _libsemigroups_pybind11.FpSemigroup) → bool

Checks if a KnuthBendix instance is being used to compute the finitely presented semigroup.

Returns

A bool.

has_todd_coxeter(self: _libsemigroups_pybind11.FpSemigroup) → bool

Checks if a ToddCoxeter instance is being used to compute the finitely presented semigroup.

Returns

A bool.

identity(self: _libsemigroups_pybind11.FpSemigroup) → str

Returns the identity of this, or raises an exception if there isn't one.

Returns

A string.

inverses(self: _libsemigroups_pybind11.FpSemigroup) → str

Returns the inverses of this, or raises an exception if there aren't any.

Returns

A string.

is_obviously_finite(self: _libsemigroups_pybind11.FpSemigroup) → bool

Return True if the finitely presented semigroup is obviously finite, and False if it is not obviously finite.

Returns

A bool.

is_obviously_infinite(self: _libsemigroups_pybind11.FpSemigroup) → bool

Return True if the finitely presented semigroup is obviously infinite, and False if it is not obviously infinite.

Returns

A bool.

kill(self: libsemigroups::Runner) → None

Stop the algorithm from running (thread-safe).

Returns

(None).

knuth_bendix(self: _libsemigroups_pybind11.FpSemigroup) → libsemigroups::fpsemigroup::KnuthBendix

Returns the KnuthBendix instance used to compute the finitely presented semigroup (if any).

Returns

A KnuthBendix instance.

normal_form(*args, **kwargs)

Overloaded function.

  1. normal_form(self: _libsemigroups_pybind11.FpSemigroup, w: str) -> str

    Returns a normal form for a string.

    Parameters

    w (str) - the word whose normal form we want to find. The parameter w must consist of letters in alphabet().

    Returns

    A string.

  2. normal_form(self: _libsemigroups_pybind11.FpSemigroup, w: List[int]) -> List[int]

    Returns a normal form for a list of integers.

    Parameters

    w (List[int]) - the word whose normal form we want to find. The parameter w consist of indices of the generators of the finitely presented semigroup that self represents.

    Returns

    A list of integers.

number_of_rules(self: _libsemigroups_pybind11.FpSemigroup) → int

Returns the number of rules currently used to define the finitely presented semigroups.

Returns

An int.

report(self: _libsemigroups_pybind11.FpSemigroup) → bool

Check if it is time to report.

Returns

A bool.

report_every(self: _libsemigroups_pybind11.FpSemigroup, t: datetime.timedelta) → None

Set the minimum elapsed time between reports.

Parameters

t (datatime.timedelta) - the amount of time between reports.

Returns

(None)

report_why_we_stopped(self: _libsemigroups_pybind11.FpSemigroup) → None

Report why the algorithm stopped.

Returns

(None)

rules(self: _libsemigroups_pybind11.FpSemigroup) → Iterator

Returns an iterator to the rules used to define the finitely presented semigroup.

Returns

An iterator.

run(self: _libsemigroups_pybind11.FpSemigroup) → None

Run the algorithm.

Returns

(None)

run_for(self: _libsemigroups_pybind11.FpSemigroup, t: datetime.timedelta) → None

Run for a specified amount of time.

Parameters

t (datetime.timedelta) - the time to run for.

Returns

(None)

run_until(self: _libsemigroups_pybind11.FpSemigroup, func: Callable[[], bool]) → None

Run until a nullary predicate returns True or the algorithm is finished.

Parameters

func (Callable[], bool) - the nullary predicate.

Returns

(None)

running(self: _libsemigroups_pybind11.FpSemigroup) → bool

Check if the algorithm is currently running.

Returns

True if algorithm is in the process of running and False it is not.

set_alphabet(*args, **kwargs)

Overloaded function.

  1. set_alphabet(self: _libsemigroups_pybind11.FpSemigroup, n: int) -> None

    Set the size of the alphabet.

    Parameters

    n (int) - the number of letters.

    Returns

    (None)

  2. set_alphabet(self: _libsemigroups_pybind11.FpSemigroup, a: str) -> None

    Set the alphabet of the finitely presented semigroup.

    Parameters

    a (str) - the alphabet.

    Returns

    (None)

set_identity(*args, **kwargs)

Overloaded function.

  1. set_identity(self: _libsemigroups_pybind11.FpSemigroup, id: int) -> None

    Set a string of length 1 belonging to alphabet() to be the identity using its index.

    Parameters

    id (int) - the index of the character to be the identity.

    Returns

    (None)

  2. set_identity(self: _libsemigroups_pybind11.FpSemigroup, id: str) -> None

    Set a string of length 1 belonging to alphabet() to be the identity.

    Parameters

    id (str) - a string containing the character to be the identity.

    Returns

    (None)

set_inverses(self: _libsemigroups_pybind11.FpSemigroup, a: str) → None

Set the inverses of letters in alphabet().

Parameters

a (str) -- a string of length alphabet().size().

Returns

(None)

size(self: _libsemigroups_pybind11.FpSemigroup) → int

Returns the size of the finitely presented semigroup.

Returns

An int the value of which equals the size of this if this number is finite, or POSITIVE_INFINITY if this number is not finite.

started(self: _libsemigroups_pybind11.FpSemigroup) → bool

Check if the algorithm has started.

Returns

A bool.

stopped(self: _libsemigroups_pybind11.FpSemigroup) → bool

Check if the algorithm is stopped.

Returns

A bool.

stopped_by_predicate(self: _libsemigroups_pybind11.FpSemigroup) → bool

Check if the runner was, or should, stop because the nullary predicate passed as first argument to run_until() return True.

Returns

A bool.

string_to_word(self: _libsemigroups_pybind11.FpSemigroup, w: str) → List[int]

Convert a string to a list of integers representing the same element of the finitely presented semigroup.

Parameters

w (str) -- the string to convert.

Returns

A list of integers.

timed_out(self: _libsemigroups_pybind11.FpSemigroup) → bool

Check if the amount of time specified to run_for() has elapsed.

Returns

A bool.

to_gap_string(self: _libsemigroups_pybind11.FpSemigroup) → str

Returns a string containing GAP commands for defining a finitely presented semigroup equal to that represented by self.

Returns

A string.

todd_coxeter(self: _libsemigroups_pybind11.FpSemigroup) → libsemigroups::CongruenceWrapper<libsemigroups::congruence::ToddCoxeter>

Returns the ToddCoxeter instance used to compute the finitely presented semigroup (if any).

Returns

A ToddCoxeter instance.

uint_to_char(self: _libsemigroups_pybind11.FpSemigroup, a: int) → str

Convert an int to a string of length 1 representing the same generator of the finitely presented semigroup.

Parameters

a (int) -- the int to convert.

Returns

A string of length 1.

validate_letter(*args, **kwargs)

Overloaded function.

  1. validate_letter(self: _libsemigroups_pybind11.FpSemigroup, c: str) -> None

    Validates a letter.

    Parameters

    c (str) - the letter to validate.

    Returns

    (None)

  2. validate_letter(self: _libsemigroups_pybind11.FpSemigroup, c: int) -> None

    Validates a letter.

    Parameters

    c (int) - the letter to validate.

    Returns

    (None)

validate_word(*args, **kwargs)

Overloaded function.

  1. validate_word(self: _libsemigroups_pybind11.FpSemigroup, w: List[int]) -> None

    Validates a word.

    Parameters

    w (List[int]) - the word to validate.

    Returns

    (None)

  2. validate_word(self: _libsemigroups_pybind11.FpSemigroup, w: str) -> None

    Validates a word.

    Parameters

    w (str) - the word to validate.

    Returns

    (None)

word_to_string(self: _libsemigroups_pybind11.FpSemigroup, w: List[int]) → str

Convert a list of integers to a string representing the same element of the finitely presented semigroup.

Parameters

w (List[int]) -- the word to convert.

Returns

A string.