Orders

This page contains the documentation for several functions for comparing words or strings with respect to certain reduction orderings.

See also

Order.

Contents

lexicographical_compare(…)

Compare two values of type str or list[int] using using lexicographical ordering.

recursive_path_compare(…)

Compare two values of type str or list[int] using recursive-path ordering.

shortlex_compare(…)

Compare two values of type str or list[int] using shortlex ordering.

Full API

lexicographical_compare(x: str | list[int], y: str | list[int]) → bool

Compare two values of type str or list[int] using using lexicographical ordering.

Parameters:

  • x (str | list[int]) – the first object for comparison.

  • y (str | list[int]) – the second object for comparison.

Returns:

The boolean value True if x is lexicographically less than y, and False otherwise.

Return type:

bool

Complexity:

At most \(O(n)\) where \(n\) is the minimum of the length of x and the length of y.

recursive_path_compare(x: str | list[int], y: str | list[int]) → bool

Compare two values of type str or list[int] using recursive-path ordering.

Compare two values of type str or list[int] using the recursive path comparison described in [Jan12] (Definition 1.2.14, page 24).

If \(u, v\in X ^ {*}\), \(u \neq v\), and \(u = a'u\), \(v = bv'\) for some \(a,b \in X\), \(u',v'\in X ^ {*}\), then \(u > v\) if one of the following conditions holds:

  1. \(a = b\) and \(u' \geq v'\);

  2. \(a > b\) and \(u > v'\);

  3. \(b > a\) and \(u' > v\).

This documentation and the implementation of recursive_path_compare is based on the source code of [Hol19].

Parameters:

  • x (str | list[int]) – the first object for comparison.

  • y (str | list[int]) – the second object for comparison.

Returns:

The boolean value True if x is less than y with respect to the recursive path ordering, and False otherwise.

Return type:

bool

Warning:

This function has significantly worse performance than shortlex_compare and lexicographical_compare.

shortlex_compare(x: str | list[int], y: str | list[int]) → bool

Compare two values of type str or list[int] using shortlex ordering.

Parameters:

  • x (str | list[int]) – the first object for comparison.

  • y (str | list[int]) – the second object for comparison.

Returns:

The boolean value True if x` is short-lex less than y, and False otherwise.

Return type:

bool

Complexity:

At most \(O(n)\) where \(n\) is the minimum of the length of x and the length of y.