Ученые записки математических кафедр вып. 1970 г.

' -ш - Отметмн далее, что поскольку Ь является интервалов; то О не ножет; по условно I) быть интервалом," Следовательно',1 С(О) > 1 и нампроцесс построения новых множеств элементов^ равных И, начинающихся с О. И ^ обязательно обрывается через меньше, чем £ (аИ^) шагов. Пусть 77? = Ц Л1£• Как обьединеняе конечного числа конечных множеств, каждое из которых можно эффективно найти- У1 само является конечным множеством; которое можно эффективно найти/ Дня окончания доказательства леммы,г,- остается показать; что 1ТС = и . Ео из построения 777 ясно; что если V £ УТС те \/= и .Поэтому достаточно доказать; что 7 7 /замкнуто относительно применения дополнительных определяющих соотношение. Действительно, такое применение к элементу вида а Ц/^. даёт элемент из Д1 у ( если оно затрагивает а ) или элемент вида и Ц/г црщ Ц=<^ ( есдн оно не затрагивает а ). Каждый другой эхемент множества УТС имеет вид • где все условия леммы I выполнявтся.' Коли применение дополнительного определяющего соотношения к тако! элементу 1л/ затрагивает С£- С * С и \л]* то он* даёт элемент множества \л/си Ясли оно затрагивает но не затрагивает IV" * то но лемме I он. является заменой на равное ему дополнив телыо* определяющее слово жпоэтому дает элемент » /Л ИМ Если же «но затрагивает IV ” * но не затрагивает с /У ' с ‘ то оно дает элемент из некоторого множества М при * г <( Демма 2 дожевала.’ ломма 3.’ Полугруппа (А удовлетворяет условию б). Доказательство; Существование алгоритма для ремевия проблем тождества слов непосредственно следует на леммы * раэреии- МОСТ! этой проблемыдля а-г (