Presentation helpers

Defined in present.hpp and knuth-bendix.hpp.

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

These functions are available in the present.hpp file except redundant_rule which is in knuth-bendix.hpp.

Contents

add_rule

Add a rule to the presentation.

add_rule_and_check

Add a rule to the presentation and check.

add_identity_rules

Add rules for an identity element.

add_inverse_rules

Add rules for inverses.

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_1v_1 < \cdots < u_nv_n\) where \(<\) is the shortlex order.

change_alphabet

Change or re-order the alphabet.

character

Return a char by index (ordered for readability).

first_unused_letter

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

greedy_reduce_length

Greedily reduce the length of the presentation using longest_common_subword.

is_strongly_compressible

Returns true if the 1-relation presentation can be strongly compressed.

length

Return the sum of the lengths of the rules.

letter

Return a possible letter by index.

longest_common_subword

Returns the longest common subword of the rules.

longest_rule

Returns an iterator pointing at the left hand side of the first rule of maximal length.

longest_rule_length

Returns the maximum length of a rule.

make_semigroup

Convert a monoid presentation to a semigroup presentation.

normalize_alphabet

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

reduce_complements

If there are rules \(u = v\) and \(v = w\) where \(|w| < |v| `, then replace :math:`u = v\) by \(u = w\).

reduce_to_2_generators

Reduce the number of generators in a f$1f$-relation presentation to 2.

redundant_rule

Return an iterator pointing at 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 word in every rule.

shortest_rule

Returns an iterator pointing at the left hand side of the first rule of minimal length.

shortest_rule_length

Returns the minimum length of a 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_1v_1 < \cdots < u_nv_n\).

strongly_compress

Strongly compress a 1-relation presentation.

Full API

Warning

doxygennamespace: Cannot find namespace “libsemigroups::presentation” in doxygen xml output for project “libsemigroups” from directory: ../build/xml