Presentation helpers¶

This page contains the documentation for various helper functions for manipulating Presentation objects. All such functions are contained in the submodule libsemigroups_pybind11.presentation.

Contents¶

`add_identity_rules()`	Add rules for an identity element.
`add_inverse_rules()`	Add rules for inverses.
`add_rule_and_check()`	Add a rule to the presentation by reference and check.
`add_rule()`	Add a rule to the presentation.
`add_rules()`	Add a rule to the presentation from another presentation.
`add_zero_rules()`	Add rules for a zero element.
`are_rules_sorted()`	Check if the rules \(u_1 = v_1, \ldots, u_n = v_n\) satisfy \(u_1 v_1 < \cdots < u_n v_n\), where \(<\) is the shortlex order.
`change_alphabet()`	Change or re-order the alphabet.
`character()`	Return a possible character by index.
`first_unused_letter()`	Return a possible character by index.
`greedy_reduce_length()`	Greedily reduce the length of the presentation using `longest_common_subword()`.
`is_strongly_compressible()`	Returns `True` if a \(1\)-relation presentation can be strongly compressed.
`length()`	Return the sum of the lengths of the rules.
`letter()`	Return the sum of the lengths of the rules.
`longest_common_subword()`	Return the longest common subword of the rules.
`longest_rule_length()`	Return the longest length of any rule.
`longest_rule()`	Return the index of the left hand side of the longest rule.
`make_semigroup()`	Convert a monoid presentation to a semigroup presentation.
`make()`	Make a presentation from another type of presentation or a `FroidurePin` instance.
`normalize_alphabet()`	Modify the presentation so that the alphabet is \(\{0, \ldots, n - 1\}\) (or equivalent), and rewrites the rules to use this alphabet.
`reduce_complements()`	If there are rules \(u = v\) and \(v = w\) where \(\lvert w \rvert < \lvert v \rvert\), then replace \(u = v\) with \(u = w\).
`reduce_to_2_generators()`	Reduce the number of generators in a \(1\)-relation presentation to `2`.
`redundant_rule()`	Returns the index of the left hand side of a redundant rule.
`remove_duplicate_rules()`	Remove duplicate rules.
`remove_redundant_generators()`	Remove any trivially redundant generators.
`remove_trivial_rules()`	Remove rules consisting of identical words.
`replace_subword()`	Replace non-overlapping instances of a subword.
`replace_word()`	Replace instances of a word occupying either side of a rule.
`reverse()`	Reverse every rule.
`shortest_rule_length()`	Return the shortest length of any rule.
`shortest_rule()`	Return the index of the left hand side of the shortest rule.
`sort_each_rule()`	Sort each rule \(u = v\) so that the left hand side is shortlex greater than the right hand side.
`sort_rules()`	Sort the rules \(u_1 = v_1, \ldots, u_n = v_n\) so that \(u_1 v_1 < \cdots < u_n v_n\), where \(<\) is the shortlex order.
`strongly_compress()`	Strongly compress a \(1\)-relation presentation.

Full API¶

add_identity_rules(p: Presentation, e: Union[str, int]) → None¶

Add rules for an identity element.

Adds rules of the form \(a e = e a = a\) for every letter \(a\) in the alphabet of p, where \(e\) is the second parameter.

Parameters

p (Presentation) -- the presentation to add rules to
e (str or int) -- the identity element

Returns

None

>>> from libsemigroups_pybind11 import presentation, Presentation
>>> p = Presentation("abc")
>>> presentation.add_identity_rules(p, "c")
>>> p.rules
['ac', 'a', 'ca', 'a', 'bc', 'b', 'cb', 'b', 'cc', 'c']

add_inverse_rules(p: Presentation, vals: Union[str, List[int], e: Union[str, int]) → None¶

Add rules for inverses.

The letter a with index i in vals is the inverse of the letter in the alphabet of p with index i. The rules added are \(a_i b_i = e\), where the alphabet is \(\{a_i, \ldots, a_n\}\); the parameter vals is \(\{b_1, \ldots, b_n\}\); and \(e\) is the 3rd parameter.

Parameters

p (Presentation) -- the presentation to add rules to
vals (str or List[int]) -- the inverses
e (str or int) -- the identity element

Returns

None

>>> from libsemigroups_pybind11 import presentation, Presentation
>>> p = Presentation("abc")
>>> presentation.add_inverse_rules(p, "bac", "c")
>>> p.rules
['ab', 'c', 'ba', 'c']

add_rule_and_check(p: Presentation, lhop: Union[str, List[int]], rhop: Union[str, List[int]]) → None¶

Add a rule to the presentation, and check that it is valid.

Adds the rule with left hand side lhop and right hand side rhop to the rules, after checking that lhop and rhop consist entirely of letters in the alphabet of p (see Presentation.validate_rules()).

Parameters

p (Presentation) -- the presentation
lhop (str or List[int]) -- the left hand side of the rule
rhop (str or List[int]) -- the right hand side of the rule

Returns

None

add_rule(p: Presentation, lhop: Union[str, List[int]], rhop: Union[str, List[int]]) → None¶

Add a rule to the presentation.

Adds the rule with left hand side lhop and right hand side rhop to the rules.

Parameters

p (Presentation) -- the presentation
lhop (str or List[int]) -- the left hand side of the rule
rhop (str or List[int]) -- the right hand side of the rule

Returns

None

Warning

No checks that the arguments describe words over the alphabet of the presentation are performed.

>>> from libsemigroups_pybind11 import presentation, Presentation
>>> p = Presentation("ab")
>>> p.rules
[]
>>> presentation.add_rule(p, "ab", "baa")
>>> p.rules
['ab', 'baa']
>>> presentation.add_rule(p, "aaa", "a")
>>> p.rules
['ab', 'baa', 'aaa', 'a']

add_rules(p: Presentation, q: Presentation) → None¶

Add all the rules from one presentation to another presentation.

Adds all the rules of the second argument to the first argument, which is modified in-place.

Parameters

p (Presentation) -- the presentation to add rules to
q (Presentation) -- the presentation with the rules to add

Returns

None

>>> from libsemigroups_pybind11 import presentation, Presentation
>>> p = Presentation("ab")
>>> presentation.add_rule(p, "ab", "baa")
>>> presentation.add_rule(p, "aaa", "a")
>>> p.rules
['ab', 'baa', 'aaa', 'a']
>>> q = Presentation("ab")
>>> presentation.add_rule(q, "bbbb", "b")
>>> q.rules
['bbbb', 'b']
>>> presentation.add_rules(p, q)
>>> p.rules
['ab', 'baa', 'aaa', 'a', 'bbbb', 'b']
>>> q.rules
['bbbb', 'b']

add_zero_rules(p: Presentation, z: Union[str, int]) → None¶

Add rules for a zero element.

Adds rules of the form \(a z = z a = z\) for every letter \(a\) in the alphabet of p, where \(z\) is the second parameter.

Parameters

p (Presentation) -- the presentation to add rules to
z (str or int) -- the zero element

Returns

None

>>> from libsemigroups_pybind11 import presentation, Presentation
>>> p = Presentation("abc")
>>> presentation.add_zero_rules(p, "c")
>>> p.rules
['ac', 'c', 'ca', 'c', 'bc', 'c', 'cb', 'c', 'cc', 'c']

are_rules_sorted(p: Presentation) → None¶

Check if the rules \(u_1 = v_1, \ldots, u_n = v_n\) satisfy \(u_1 v_1 < \cdots < u_n v_n\), where \(<\) is the shortlex order.

Parameters: p (Presentation) -- the presentation to check
Returns: True if the rules are sorted, and False if not.

change_alphabet(p: Presentation) → None¶

Change or re-order the alphabet.

This function replaces p.alphabet() with new_alphabet, where possible, and re-writes the rules in the presentation using the new alphabet.

Parameters

p (Presentation) -- the presentation
new_alphabet (Union[str, List[int]]) -- the replacement alphabet

Returns

None.

Raises

RuntimeError -- if the size of p.alphabet() and new_alphabet do not agree.

character(i: int) → str¶

Return a possible character by index.

This function returns the i-th letter in the alphabet consisting of all possible characters. This function exists so that visible ASCII characters occur before invisible ones, so that when manipulating presentations over strings the human readable characters are used before non-readable ones.

Parameters: i (int) -- the index
Returns: A str.
Raises: RuntimeError -- if i exceeds the number of letters in supported by str.

See also

letter()

first_unused_letter(p: Presentation) → Union[str, int]¶

Returns the first letter not in the alphabet of a presentation.

This function returns :py:func:letter(p, i) when i is the least possible value such that p.in_alphabet(letter(p, i)) returns False if such a letter exists.

Parameters: p (Presentation) -- the presentation
Returns: A str or an int depending on p.
Raises: RuntimeError -- if p already has an alphabet of the maximum possible size supported.

greedy_reduce_length(p: Presentation) → None¶

Greedily reduce the length of the presentation using longest_common_subword().

This function repeatedly calls longest_common_subword() and replace_subword() to introduce a new generator and reduce the length of the presentation p until longest_common_subword() returns the empty word.

Parameters: p (Presentation) -- the presentation
Returns: None
Raises: RuntimeError -- if longest_common_subword() or replace_word() does.

is_strongly_compressible(p: Presentation) → bool¶

Returns True if the \(1\)-relation presentation can be strongly compressed.

A \(1\)-relation presentation is strongly compressible if both relation words start with the same letter and end with the same letter. In other words, if the alphabet of the presentation p is \(A\) and the relation words are of the form \(aub = avb\) where \(a, b\in A\) (possibly \(a = b\)) and \(u, v\in A^*\), then p is strongly compressible. See Section 3.2 for details.

Parameters: p (Presentation) -- the presentation
Returns: A value of type bool.

See also

strongly_compress()

length(p: Presentation) → int¶

Return the sum of the lengths of the rules.

Parameters: p (Presentation) -- the presentation
Returns: An int.

letter(p: Presentation, i: int) → int¶

Return a possible letter by index.

This function returns the i-th letter in the alphabet consisting of all possible letters of type Presentation.letter_type. This function exists so that visible ASCII characters occur before invisible ones, so that when manipulating presentations over strings the human readable characters are used before non-readable ones.

Parameters

p (Presentation) -- a presentation
i (int) -- the index

Returns

A str.

Raises

RuntimeError -- if i exceeds the number of letters in supported by str.

See also

character()

longest_common_subword(p: Presentation) → Union[str, List[int]]¶

Return the longest common subword of the rules.

If it is possible to find a subword \(w\) of the rules \(u_1 = v_1, \ldots, u_n = v_n\) such that the introduction of a new generator \(z\) and the relation \(z = w\) reduces the length (see length()) of the presentation, then this function returns the word \(w\). If no such word can be found, a word of length \(0\) is returned.

Parameters: p (Presentation) -- the presentation
Returns: str or List[int]

longest_rule_length(p: Presentation) → int¶

Returns the maximum length of a rule in the presentation.

The length of a rule is defined to be the sum of the lengths of its left and right hand sides.

Parameters: p (Presentation) -- the presentation
Returns: An int.
Raises: RuntimeError -- if the length of p.rules is odd.

longest_rule(p: Presentation) → int¶

Returns the index of the left hand side of the first rule in the presentation with maximal length.

The length of a rule is defined to be the sum of the lengths of its left and right hand sides.

Parameters: p (Presentation) -- the presentation
Returns: An int.
Raises: RuntimeError -- if the length of p.rules is odd.

make_semigroup(p: Presentation) → Union[int, str]¶

Convert a monoid presentation to a semigroup presentation.

This function modifies its argument in-place by replacing the empty word in all relations by a new generator, and the identity rules for that new generator. If p.contains_empty_word() is False, then the presentation is not modified and UNDEFINED is returned. If a new generator is added as the identity, then this generator is returned.

Parameters: p (Presentation) -- the presentation
Returns: the new generator added, if any, and UNDEFINED if not.
Raises: RuntimeError -- if replace_word() or add_identity_rules() does.

make(p: Presentation) → Presentation¶

Converts a presentation over strings to one over lists of integers or vice versa.

Parameters: p (Presentation) -- the presentation
Returns: A Presentation.

make(S: FroidurePin) → Presentation

Returns a presentation defining a semigroup isomorphic to that represented by a FroidurePin instance.

Parameters: S (FroidurePin) -- the FroidurePin instance.
Returns: A Presentation.

normalize_alphabet(p: Presentation) → None¶

Modify the presentation so that the alphabet is \(\{0, \ldots, n - 1\}\) (or equivalent), and rewrites the rules to use this alphabet.

If the alphabet is already normalized, then no changes are made to the presentation.

Parameters: p (Presentation) -- the presentation
Returns: None

reduce_complements(p: Presentation) → None¶

If there are rules \(u = v\) and \(v = w\) where \(\lvert w \rvert < \lvert v \rvert\), then replace \(u = v\) with \(u = w\).

Attempts to reduce the length of the words by finding the equivalence relation on the relation words generated by the pairs of identical relation words. If \(\{u_1, u_2, \ldots, u_n\}\) are distinct words in an equivalence class and \(u_1\) is the shortlex minimum word in the class, then the relation words are replaced by \(u_1 = u_2, u_1 = u_3, \ldots, u_1 = u_n\).

Parameters: p (Presentation) -- the presentation
Returns: None

>>> from libsemigroups_pybind11 import presentation, Presentation
>>> p = Presentation("a")
>>> presentation.add_rule(p, "aaaaa", "aaa")
>>> presentation.add_rule(p, "aaa", "a")
>>> p.rules
['aaaaa', 'aaa', 'aaa', 'a']
>>> presentation.reduce_complements(p)
>>> p.rules
['a', 'aaa', 'a', 'aaaaa']

reduce_to_2_generators(p: Presentation) → None¶

Reduce the number of generators in a \(1\)-relation presentation to 2.

Returns True if the \(1\)-relation presentation p has been modified and False if not.

A \(1\)-relation presentation is left cycle-free if the relation words start with distinct letters. In other words, if the alphabet of the presentation p is \(A\) and the relation words are of the form \(au = bv\) where \(a, b\in A\) with \(a \neq b\) and \(u, v \in A^*\), then p is left cycle-free. The word problem for a left cycle-free \(1\)-relation monoid is solvable if the word problem for the modified version obtained from this function is solvable.

Parameters

p (Presentation) -- the presentation
x (int) -- determines the choice of letter to use, 0 uses p.rules[0].front() and 1 uses p.rules[1].front() (defaults to: 0).

Returns

A value of type bool.

Raises

RuntimeError -- if index is not 0 or 1.

redundant_rule(p: Presentation, t: datetime.timedelta) → int¶

Return the index of the the left hand side of a redundant rule.

Starting with the last rule in the presentation, this function attempts to run the Knuth-Bendix algorithm on the rules of the presentation except for the given omitted rule. For every such omitted rule, Knuth-Bendix is run for the length of time indicated by the second parameter t and then it is checked if the omitted rule can be shown to be redundant (rewriting both sides of the omitted rule using the other rules using the output of the, not necessarily finished, Knuth-Bendix algorithm).

If the omitted rule can be shown to be redundant in this way, then the index of its left hand side is returned.

If no rule can be shown to be redundant in this way, then len(p.rules) is returned.

Warning

The progress of the Knuth-Bendix algorithm may differ between different calls to this function even if the parameters are identical. As such this is non-deterministic, and may produce different results with the same input.

Parameters

p (Presentation) -- the presentation.
t (datetime.timedelta) -- time to run KnuthBendix for every omitted rule

Returns

The index of a redundant rule (if any).

>>> from libsemigroups_pybind11 import presentation, Presentation
>>> from datetime import timedelta
>>> p = Presentation("ab")
>>> presentation.add_rule(p, "ab", "ba")
>>> presentation.add_rule(p, "bab", "abb")
>>> t = timedelta(seconds = 1)
>>> p.rules
['ab', 'ba', 'bab', 'abb']
>>> presentation.redundant_rule(p, t)
2

remove_duplicate_rules(p: Presentation) → None¶

Remove duplicate rules.

Removes all but one instance of any duplicate rules (if any). Note that rules of the form \(u = v\) and \(v = u\) (if any) are considered duplicates. Also note that the rules may be reordered by this function even if there are no duplicate rules.

Parameters: p (Presentation) -- the presentation
Returns: None

>>> from libsemigroups_pybind11 import presentation, Presentation
>>> p = Presentation("ab")
>>> presentation.add_rule(p, "ab", "baa")
>>> presentation.add_rule(p, "baa", "ab")
>>> p.rules
['ab', 'baa', 'baa', 'ab']
>>> presentation.remove_duplicate_rules(p)
>>> p.rules
['ab', 'baa']

remove_redundant_generators(p: Presentation) → None¶

Remove any trivially redundant generators.

If one side of any of the rules in the presentation p is a letter a and the other side of the rule does not contain a, then this function replaces every occurrence of a in every rule by the other side of the rule. This substitution is performed for every such rule in the presentation; and the trivial rules (with both sides being identical) are removed. If both sides of a rule are letters, then the greater letter is replaced by the lesser one.

Parameters: p (Presentation) -- the presentation
Returns: None
Raises: RuntimeError -- if len(p.rules) is odd.

remove_trivial_rules(p: Presentation) → None¶

Remove rules consisting of identical words.

Removes all instance of rules (if any) where the left hand side and the right hand side are identical.

Parameters: p (Presentation) -- the presentation
Returns: None
Raises: RuntimeError -- if len(p.rules) is odd.

replace_subword(p: Presentation, existing: Union[str, List[int]], replacement: Union[str, List[int]]) → None

Replace non-overlapping instances of a subword by another word.

If existing and replacement are words, then this function replaces every non-overlapping instance of existing in every rule by replacement. The presentation p is changed in-place.

Parameters

p (Presentation) -- the presentation
existing (str or List[int]) -- the word to be replaced
replacement (str or List[int]) -- the replacement word.

Returns

None

Raises

RuntimeError -- if existing is empty.

replace_subword(p: Presentation, w: Union[str, List[int]]) → None¶

Replace non-overlapping instances of a subword.

A new generator \(z\) is added to the presentation, along with the rule \(w = z\). Each (if any) non-overlapping instance (from left to right) of the word \(w\) in every rule of the presentation is replaced with \(z\).

Parameters

p (Presentation) -- the presentation
w (str or List[int]) -- the word to be replaced by a new generator

Returns

None

>>> from libsemigroups_pybind11 import presentation, Presentation
>>> p = Presentation([0, 1])
>>> presentation.add_rule(p, [1, 0, 0, 1, 0], [0, 1, 0, 0, 1])
>>> p.rules
[[1, 0, 0, 1, 0], [0, 1, 0, 0, 1]]
>>> presentation.replace_subword(p, [0, 0, 1])
>>> p.rules
[[1, 2, 0], [0, 1, 2], [2], [0, 0, 1]]

replace_word(p: Presentation, existing: Union[str, List[int]], replacement: Union[str, List[int]]) → None¶

Replace instances of a word occupying either side of a rule.

If existing and replacement are words, then this function replaces every instance of existing in every rule of the form existing \(= w\) or \(w =\) existing, with the word replacement. The presentation p is changed in-place.

Parameters

p (Presentation) -- the presentation
existing (str or List[int]) -- the word to be replaced
replacement (str or List[int]) -- the replacement word

Returns

None

reverse(p: Presentation) → None¶

Reverse every rule.

Parameters: p (Presentation) -- the presentation
Returns: None

shortest_rule_length(p: Presentation) → int¶

Returns the minimum length of a rule in the presentation.

The length of a rule is defined to be the sum of the lengths of its left and right hand sides.

Parameters: p (Presentation) -- the presentation
Returns: An int.
Raises: RuntimeError -- if the length of p.rules is odd.

shortest_rule(p: Presentation) → int¶

Returns the index of the left hand side of the first rule in the presentation with minimal length.

The length of a rule is defined to be the sum of the lengths of its left and right hand sides.

Parameters: p (Presentation) -- the presentation
Returns: An int.
Raises: RuntimeError -- if the length of p.rules is odd.

sort_each_rule(p: Presentation) → None¶

Sort each rule \(u = v\) so that the left hand side is shortlex greater than the right hand side.

Parameters: p (Presentation) -- the presentation
Returns: None

sort_rules(p: Presentation) → None¶

Sort the rules \(u_1 = v_1, \ldots, u_n = v_n\) so that \(u_1 < \cdots < u_n\), where \(<\) is the shortlex order.

Parameters: p (Presentation) -- the presentation
Returns: None

strongly_compress(p: Presentation) → None¶

Strongly compress a \(1\)-relation presentation.

Returns True if the \(1\)-relation presentation p has been modified and False if not. The word problem is solvable for the input presentation if it is solvable for the modified version.

Parameters: p (Presentation) -- the presentation
Returns: A value of type bool.

See also

is_strongly_compressible()