An efficient algorithm to decide whether a monoid presented by a regular Church-Rosser Thue system is a group (Q1123272)

From MaRDI portal
scientific article
Language Label Description Also known as
English
An efficient algorithm to decide whether a monoid presented by a regular Church-Rosser Thue system is a group
scientific article

    Statements

    An efficient algorithm to decide whether a monoid presented by a regular Church-Rosser Thue system is a group (English)
    0 references
    1989
    0 references
    Let T be a Thue system on the finite alphabet A. \(| A|\) stands for the cardinality of A and \(| T|\) is the size of the Thue system. If a regular Church-Rosser Thue system on A is given, an \(O(| A|^ 2\times | T|)\) algorithm is presented for computing whether the monoid \(M_ T\) presented by T is a group.
    0 references
    alphabet
    0 references
    regular Church-Rosser Thue system
    0 references
    algorithm
    0 references
    monoid
    0 references
    group
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references