66.8 Counting and enumerating irreducible words

SizeRWS(rws)

Returns the number of irreducible words in the rewriting system rws. If this is infinite, then the string ``infinite" is returned.

SizeRWS can only be used after KB or Automata has been run successfully on rws. In the former case, if KB halted without a confluent set of rules, then the number of irreducible words may be greater than the number of words in normal form (which is equal to the order of the underlying group of rws). If KB completes with a confluent rewriting system or Automata completes successfully, then it is guaranteed that SizeRWS will return the correct order of the underlying group.

EnumerateRWS(rws, min, max)

Enumerate all irreducible words in the rewriting system rws that have lengths between min and max (inclusive), which should be non-negative integers. The result is returned as a list of words. The enumeration is by depth-first search of a finite state automaton, and so the words in the list returned are ordered lexicographically (not by shortlex).

EnumerateRWS can only be used after KB or Automata has been run successfully on rws. In the former case, if KB halted without a confluent set of rules, then not all irreducible words in the list returned will necessarily be in normal form. If KB completes with a confluent rewriting system or Automata completes successfully, then it is guaranteed that all words in the list will be in normal form.

SortEnumerateRWS(rws, min, max)

This is the same as EnumerateRWS but the list returned contains the words in shortlex order; so shorter words come before longer ones. It is slightly slower than EnumerateRWS.

SizeEnumerateRWS(rws, min, max)

This returns the length of the list that would be returned by EnumerateRWS(rws, min, max); that is, the number of irreducible words of rws that have lengths between min and max inclusive. It is faster than EnumerateRWS, since it does not need to store the words enumerated.

Previous Up Top Next
Index

GAP 3.4.4
April 1997