Попов В. Ю.
О сложности проблемы равенства для конечно определенных коммутативных полугрупп

Для любой конечно определенной коммутативной полугруппы проблема равенства распознаваема на машине Тьюринга реального времени.

Popov V. Yu.
On complexity of the word problem for finitely presented commutative semigroups

The word problem is tractable on a real-time Turing machine for every finitely presented commutative semigroup.

Полный текст статьи / Full texts:

• PDF file (405 KB)
• PostScript file (816 KB)