Проблема тождества в полугруппах.

[stiv]

Есть теорема: проблема равенства слов в полугруппах алгоритмически неразрешима.
Но что есть равенство слов в полугруппе, если её элементы - классы эквивалентности по отношению достижимости в туэвской системе двусторонних правил? Как мы можем сравнивать классы эквивалентности?

[arseniiv]

Классы эквивалентности — как любые другие множества, по содержанию (и даже чуть удобнее: если элемент одного класса есть в другом, то они, ясно, сразу же равны).