Рекурсивно отделимые нумерованные алгебры тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

•РОССИЙСКАЯ СИБИРСКО ИНСТИТУТ

АКАДЕМИЯ НАУК Е ОТДЕЛЕНИЕ МАТЕМАТИКИ

На правах рукописи

Касымов Надимулла Хабибуллаевич

РЕКУРСИВНО ОТДЕЛИМЫЕ НУМЕРОВАННЫЕ АЛГЕБРЫ

01.01.06 - математическая логика, алгебра и теория чисел

Автореферат

диссертации на соискание ученой степени доктора физико-математических наук

Новосибирск - 1993

Работа выполнена на кафедре алгебры и математической логики Новосибирского государственного университета

Научный консультант: доктор физико-математических

наук, профессор С.С.Гончаров Официальные оппоненты: доктор физико-математических

наук, профессор A.A. Никитин, доктор физико-математических наук, профессор А.Л. Сембнов, доктор физико-математических наук, профессор Н.Г.Хисамиев.

Ведущая организация: Уральский государственный университет

Защита состоится - 1993 г.

в час.30 мин. на заседании специализированного совета Д 002.23.01 по защите диссертаций на соискание ученой степени доктора физико-математических наук при Институте математики СО РАН по адресу : 630090, Новосибирск-90, Университетский пр. 4.

С диссертацией можно ознакомиться в библиотеке Института математики СО РАН

Автореферат разослан "—" —— 1993 г.

Ученый секретарь Специализированного совета к.ф.-м.н.

С.Т.Федоряев

Общая характеристика работы

Актуальность темы. Введенное А.И. Мальцевым в [8] понятие нумерованной алгебры - одно из центральных понятий, возникших'на стыке универсальной алгебры и теории нумераций.В силу чрезвычайной общности класса всех нумерованных алгебр изучение последних обычно проводится в предположении наличия ограничений на алгоритмические сложности нумерационных эквивалентностей. В этом аспекте, в первую очередь, нужно отметить конструктивные и позитивные алгебры, теория которых представляет собой бурно развивающийся раздел современной математической логики (Ю.Л. Е^ипов [5], С.С. Гончаров [3]). Проблемы существования и числа конструктивизаций алгебр стали уже классическими (Ю.Л. Ершов [5], С.С. Гончаров [1]), а ослабление требований к алгоритмической сложности нумерационных эквивалентностей является одним из общепринятых способов расширения исследуемого класса нумерованных алгебр.

Другой путь ограничения исследуемого класса нумерованных алгебр, который, в отличие от предыдущего, игнорирует сложность нумерационной эквивалентности, заключается в наложении, эффективных условий типа отделимости. Идеи использования понятия отделимости в теории нумераций восходят к В.А. Успенскому [14.151 и А. Нероуду [21] и развивается в работах А.И. Мальцева [9,1о] и Ю.Л. Ершова [4]. Классическим условием отделимости в теории алгоритмов является рекурсивная отделимость. Синтез понятий универсальной алгебры и рекурсивно отделимой нумерации образует понятие рекурсивно отделимой нумерованной алгебр!. Многие естественные и важные типы нумерованных алгебр оказались рекурсивно отделимыми, в том числе - среди неочевидных - негативные алгебр», позитивные алгебры со счетными решетками контруэнций, стандартно нумерованные конечно-порожденные и финитно-аппроксимируемые алгебры. Негативные нумерации и негативные алгебры с различных точек зрения исследовались А.И. Мальцевым [11], Ю.Л. Ершовым [4], A.C. Морозовым [12], С.П. Одинцовым и В.Л. Селивановым [13]. Результаты о позитивных алгебрах со счетными решетками конгру-энций можно найти у А.И. Мальцева [8], Ю.Л. Ершова [5], A.B. Кузнецова [6], В.Баура [17]. Проблематика изучения стандартно

нумерованных конечно порожденных алгебр заложена А,И. Мальцевым в [8] и дополнительно обосновывается В.А. Успенским и А.Л. Семеновым в [16], а классические образцы использования финитной аппроксимируемости для решения алгоритмических .задач алгебры представлены у.А.И. Мальцева в Г7.8] и Д. Мак-Кинси в [20].

В различных по методам доказательства и звучанию результатах о нумерований алгебрах из . упомянутых выше классов имеется немало принципиальных общих моментов, причем справедливость некоторых весьма сильных, свойств - оказалась не зависимой от сложности нумерационной эквивалентности. Эти факты становятся прозрачными именно при обобщенном взгляде на ситуацию - с точки'зрения теории рекурсивно отделимых нумерованных алгебр. На базе и•в рамках этой теории решается ряд естественных вопросов, возникших в связи с работами А.И. Мальцева [8], В.Баура [171, Д. Бергстры. и Д.Такера [18], С.Камина [19] в теории конструктивных алгебр и в теории абстрактных типов данных.

Целесообразность изучения рекурсивно отделимых нумерованных алгебр обуславливается еще одним обстоятельством. Несмотря на обширность .класс этих алгебр допускает удовлетворительные, в тех или иных смыслах, описания. Для естественных расширений этого • класса, например класса отделимых нумерованных алгебр (определение отделимой нумерации см. у ЮЛ. Ершова [4]), справедливы только релятивизированные варианты основных утверждений. В связи с этим уместно отметить, что в теории нумерованных' алгебр роль и место рекурсивно отделимых нумерованных алгебр - с точки зрения сложности от-деляицих множеств, подобны роли и месту конструктивных алгебр - с точки зрения сложности нумерационной эквивалентности.

Цель работы. Изучение наиболее общих эффективных, структурных и топологических свойств рекурсивно отделимых нумерованных алгебр и описание важнейших типов таких алгебр.

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

Научная новизна. Круг вопросов, рассмотренных в диссертации, образует новое научное направление в математической логике - изучение рекурсивно отделимых нумерованных алгебр.

Новыми являются и все основные результаты, а также постановка проблемы систематического изучения соотношений мезду эффективными свойствами эквивалентностей и абстрактными свойствами алгебр, определимых над ними.

.Основные результаты диссертации следующие:

1) Получено описание наиболее общих эффективных, структурных и топологических свойств рекурсивно отделимых нумерованных алгебр и найдены важнейшие типы-таких алгебр (негативные алгебры, стандартно нумерованные конечно-порожденные и финитно-аппроксимируемые алгебры, позитивные алгебры со счетными решетками контруэнций).

2) Получены различные характеризации негативных алгебр и изучены вопросы определимости алгебр с условиями.конечности над негативными эквивалентностями.

3) Изучены .вопросы универсальной хорновской определимости рекурсивно отделимых позитивных алгебр в классах их гомоморфных образов.

4) Изучено соответствие между абстрактными свойствами алгебр со счетными решетками конгруэнций и эффективными свойствами их позитивных нумераций.

. Практическая и теоретическая ценность. Работа имеет теоретический характер. Ее результаты могут найти применение в теории нумерованных алгебр и в теории абстрактных типов дан-• ных. •

Апробация. Результат диссертации докладывались на 8, 9, ю Всесоюзных (Москва -1986, Ленинград -1.988, Алма-Ата -1990) и 11 Межреспубликанской (Казань - 1992) конференциях по математической логике, 19 Всесоюзной алгебраической конференции (Львов -.1987),.Мевдународных конференциях ло алгебре (Новосибирск - 1989, Барнаул - 1991, Красноярск - 1993), на Всесоюзной (Новосибирск - 1988) и Межреспубликанской (Новосибирск - 1992) конференциях по прикладной логике, на семинарах "Алгебра и логика", "Теория нумераций", "Конструктивные модели" и "Прикладная логика" при ИМ СО РАН и НГУ, а также на логических и алгебраических семинарах в МГУ, УрГУ, АбхГУ, ТашГУ, ИК с ВЦ АН РУз.

Публикации. Основные результаты диссертации опубликованы в работах [22 - 49].

Объем и структура работы. Диссертация состоит из введения и четырех глав. Объем работы 205 страниц. Библиография состоит из 96 наименований.

Содержание диссертации

Во введении обосновывается актуальность проблематики, излагается история вопроса, приводятся все необходимые определения и дается обзор результатов диссертации.

Пусть т) - эквивалентность на множестве натуральных чисел и. Подмножество со называется 17-замкнутым, если вместе с каждым числом оно содержит и все ему 17-эквивалентные [4].

ОПРЕДЕЛЕНИЕ 1. Эквивалентность 17 называется рекурсивно отделимой, если всякая пара ее различных смежных классов отделяется подходящим 17-замкнутым рекурсивным множеством.

Нумерованная алгебра (нумерация) с рекурсивно отделимой нумерационной эквивалентностью также называется рекурсивно отделимой.

В первой главе изучаются общие свойства рекурсивно отделимых нумерованных алгебр. Основным результатом первого параграфа является

ТЕОРЕМА 1.1.1. Нумерованная алгебра рекурсивно отделима тогда и только тогда, когда она аппроксимируется негативными алгебрами.

СЛЕДСТВИЕ 1.1.1. Всякая рекурсивно отделимая нумерация подпрямо неразложимой алгебры является негативной.

ОПРЕДЕЛЕНИЕ 2. Нумерация бесконечного множества называется эффективно (неэффективно) бесконечной, если существует (не существует) бесконечное рекурсивное множество натуральных чисел, попарно различных по модулю нумерационной эквивалентности.

СЛЕДСТВИЕ 1.1.3. Всякая алгебра, обладающая неэффективно бесконечной рекурсивно отделимой нумерацией является финитно аппроксимируемой.

ОПРЕДЕЛЕНИЕ з. Нвединичная эквивалентность т) называется квазисовершенной, если никакая пара ее различных смежных классов не отделяется никаким 17-замкнутым рекурсивным множес-

твом.

Нумерованная алгебра (нумерация) с квазисовершенной нумерационной эквивалентностью также называется квазисовершенной. С алгоритмической точки зрения квазисовершенные нумерации являются "антиподами" рекурсивно отделимых нумераций.

СЛЕДСТВИЕ 1.1.5. Всякая нумерованная простая алгебра либо негативна, либо квазисовершенна.

Во втором параграфе доказывается рекурсивная отделимость стандартных нумераций конечно-порожденных и финитно-аппроксимируемых алгебр и приводится ряд следствий этого факта. В частности, показывается эквивалентность свойств рекурсивной отделимости и финитной аппроксимируемости для неэффективно бесконечных конечно-поровденных алгебр.

В третьем параграфе дается топологическая характеризация рекурсивно отделимых нумераций. Для нумерации V (эквивалентности г]) естественно определяется топологическое пространство, пороаденное v-впoлнe рекурсивными ( т)-замкнутыми рекурсивными ) множествами. Это пространство будем называть v-пpocтpaнcтвoм ( т)-пространством ), а соответствующую топологию - т-топологией ( т)-топологией ). Операции любой нумерованной алгебры (й,г>) непрерывны в у-топологии, а гомоморфизм любых нумерованных алгебр, являющийся морфизмом нумерованных множеств, есть непрерывное отображение соответствующих топологических пространств.

ТЕОРЕМА 1.3.1. Нумерация V ( эквиваленпюсть т}) рекурсивно отделима тогда и только тогда, когда ^-пространство ( т)-пространство ) совершенно нормально,и вполне несвязно.

ЗАМЕЧАНИЕ. Для отделимых нумераций (при рассмотрении пространств, порожденных у-вполне перечислимыми множествами) вообще говоря не имеет места даже Т(-отделимость. Простейшим примером является связное двоеточие.

ОПРЕДЕЛЕНИЕ 4. Алгебра называется определимой над эквивалентностью т], если существует нумерация этой алгебры с нумерационной эквивалентностью равной г¡.

Определимость алгебры а над эквивалентностью т] равносильна существованию такого вычислимого семейства ? рекурсивных функций, согласованных с т), что а изоморфна фактор-алгебре рекурсивной алгебры (ш,Р) по конгруэнции т}.

Для всякого а с и обозначим через т^ эквивалентность а? и id ш[4]. Алгебры, определимые над т^ для походящих коим-мунных а оказались полезными для решения двух, вопросов А.И. Мальцева в четвертой главе.

ТЕОРЕМА 1.3.2. Для любого а с ш равносильны следующие условия:

1) а коконечно или коиммунно;

2) всякая алгебра, определимая над т^ финитно-аппрокси- . мируема;

3) т^-пространство компакт.

В четвертом параграфе вводится и изучается важное понятие равномерно рекурсивно отделимой нумерации.

ОПРЕДЕЛЕНИЕ 5. Нумерация v ( эквивалентность т}) называется равномерно рекурсивно отделимой, если существует алгоритм, значение которого на каждой паре <х,у> при vx/vy ( при х/у (mod. т]) ) определено и равно характеристическому индексу v-вполне рекурсивного (т)-замкнутого рекурсивного) множества, отделящего vx от vy (х от у).

Пусть К - подкласс класса всех негативных фактор-алгебр нумерованной алгебры (8l,v).

ОПРЕДЕЛЕНИЕ 6. (Я,г>) называется равномерно аппроксимируемой К-алгебрами, если существует алгоритм, значение которого на каадой паре <х,у> при vxtvy определено и равно перечислимому индексу К-алгебры, различающей элементы vx.vy алгебры

а.

Под перечислимым индексом негативной алгебры (93,р.) мы понимаем р.п. индекс множества {<х,у>/ цх t цу}.

Бескванторную формулу вида Аг»...»Ап —» Р, где А{-атомарные, а Р - позитивная формулы, назовем дизъюнктивно-импликативно-позитивной (ДИП-формулой). Основным результатом четвертого параграфа является

ТЕОРЕМА 1.4.3. Для нумерованной алгебры (Sl.v) равносильны следующие условия:

1) v - равномерно рекурсивно отделимая нумерация;

2) если Ф - рекурскБно-перечислимое множество универсальных ДИП-предложений, реализующееся в а, то (®,v) равномерно аппроксимируется негативными Ф-алгебрами.

В формулировке этой теоремы нельзя заменить

универсальные ДИП-предложения произвольными универсальными или экзистенциальными ДИП-предложениями, так же как нельзя опустить свойство равномерности. Отметим, что сложность равномерно рекурсивно отделимой' эквивалентности может быть какой угодно.

В пятом параграфе изучаются некоторые свойства квазисовершенных эквивалентностей и алгебр. Такие объекты представляют интерес в силу ряда причин. Например, квазисовершенными являются предполные эквивалентности, играющие важную роль в общей теории нумераций. Кроме того, как легко заметить, всякая неодноэлементная счетная алгебра эффективной сигнатуры имеет квазисовершенную нумерацию. Строится пример совершенной (т.е. квазисовершенной и позитивной [4]) конечно порожденной алгебры и рассматриваются вопросы определимости алгебр над квазисовершенными эквивалентностями.

Во второй главе изучаются негативные алгебры, образующие' важный подкласс класса рекурсивно отделимых нумерованных алгебр. Классический пример негативных нумераций - вычислимые нумерации семейств общерекурсивных функций [11]. Интересный пример негативных нумераций дают стандартные нумерации конечно-порожденных подгрупп группы рекурсивных перестановок натурального ряда.

В первом параграфе даются характеризации негативных нумераций и алгебр в классе всех нумерованных алгебр и в классе равномерно рекурсивно отделимых нумерованных алгебр.

ОПРЕДЕЛЕНИЕ 7. Характеристической трансверсально эквивалентности т] называется множество {х / х=у (mod. т)) —► х^у}.

Характеристической трансверсалью нумерации будем называть характеристическую трансверсаль ее нумерационной эквивалентности.

ТЕОРЕМА 2.1.1. Эквивалентность на множестве натуральных чисел негативна тогда и только тогда, когда она является равномерно рекурсивно отделимой эквивалентностью с рекурсивно перечислимой характеристической трансверсалью.

ТЕОРЕМА 2.1.2. Для равномерно рекурсивно отделимой нумерованной алгебры (Sl,v) равносильны следующие условия:

1) v - негативная нумерация;

2) существует такое рекурсивно-перечислимое множество а

попарно различных по модулю V натуральных1 чисел, что всякая ненулевая конгруэнция алгебры а содержит пару <ш,г>у> для подходящих различных х.у из а.

ЗАМЕЧАНИЕ. Известно ( Ю.Л. Ершов [5] ), что позитивная алгебра (Я.V) конструктивна тогда и только тогда, когда для нее выполнено условие 2 из предыдущей теоремы. Таким образом, характеризация негативных алгебр в классе равномерно рекурсивно отделимых родственна характеризации конструктивных алгебр в классе позитивных.

Во. втором параграфе рассмотрены вопросы реализуемости простейших решеток в качестве решеток конгруэнций неконструктивных негативных алгебр. Интерес к этим вопросам обусловлен тем, что, согласно В. Бауру [17]. никакая счетная артинова ( в частности конечная ) решетка не реализуется в качестве решетки .конгруэнций никакой неконструктивной позитивной алгебры. Основной результат этого параграфа представляет

ТЕОРЕМА 2.2.1. Если Ь - решетка конгруэнций конструкти-визируемой алгебры, то существует неконструктивизируемая негативно представимая конечно-поровденная алгебра, решетка конгруэнций которой изоморфна ь' (где ь'обозначает расширение ь одним элементом, интерпретируемым как единица в ь').

В частности, существуют неконструктивные негативные конечно-порожденные простые алгебры.

В третьем параграфе в определенном смысле усиливаются результаты предыдущего параграфа. Доказывается, что над всякой негативной эквивалентностью определимы как конечно-порожденные, так и простые алгебры. Для позитивных эквивалентнос-тей ни то, ни другое вообще говоря не имеет места.

СЛЕДСТВИЕ 2.2.3. Неквазисовершенная эквивалентность негативна тогда и только тогда, когда над ней определима простая алгебра.

Третья глава посвящена в основном вопросам реализуемости эффективных систем универсальных хорновских предложений в фактор-алгебрах позитивных алгебр.

В теории абстрактных типов данных принимается тезис: абстрактная структура данных - конечно-поровденная алгебра многосортной конечной сигнатуры, обладающая позитивной нумерацией. Разные стороны обоснования этого тезиса можно

найти в [2,18,19]- Проблема алгебраической специфицируемости заключается в следующем [18,19]: всякая ли абстрактная структура данных имеет обогащение, являющееся инициальной алгеброй некоторого конечно-аксиоматизируемого многообразия (квазимногообразия, позитивного класса, универсала)? В первом параграфе дается решение некоторых частных случаев проблемы алгебраической специфицируемости.

ТЕОРЕМА 3.1.1. Существует конечно-порожденная алгебра, обладающая неэффективно бесконечной, позитивной и равномерно рекурсивно отделимой нумерацией.

С учетом теоремы 1.4.3 получаем

СЛЕДСТВИЕ 3.1.1. Существует абстрактная структура данных, никакое обогащение которой не является инициальной алгеброй ни в каком конечно-аксиоматизируемом

а) квазимногообразии, задаваемом тождествами и однопосылочными квазитождествами;

б) позитивном классе.

Показано, что контрпример к проблеме алгебраической специфицируемости позитивными предложениями можно выбрать в классе эффективно бесконечных абстрактных структур данных.

Если (521 ,г>) - нумерованная алгебра, то через 5аг, обозначим стандартное г>-обогащение алгебры 21 счетным множеством констант {с0,с/, ...}, т.е. сп = Гп . Во втором параграфе доказано, что для позитивной алгебры (21,V) определимость 21^ в классе собственных (собственных позитивных) фактор-алгебр подходящим эффективным множеством универсальных (универсальных хорновских) предложений равносильна конструктивности V и приведен ряд следствий этих фактов. В частности, всякое рекурсивно-перечислимое множество универсальных хорновских предложений, реализующееся в неконструктивной позитивной алгебре, реализуется и в некоторой фактор-алгебре этой алгебры по подходящей ненулевой позитивной конгруэнции.

В третьем параграфе показывается, что подобная определимость в классе конструктивных фактор-алгебр не только возможна, но и весьма полезна.

ТЕОРЕМА 3.3.1. Всякая неконструктивная позитивная алгебра, выделяемая подходящим рекурсивно-перечислимым множеством а универсальных хорновских предложений в классе своих

конструктивных фактор-алгебр, имеет континуум конгруэнций, в фактор-алгебрах по которым также реализуется о.

Эта теорема, • имеющая ряд важных следствий, является .основным рабочим инструментом в третьем параграфе следующей главы.

Четвертая глава посвящена изучению позитивных алгебр со счетными решетками конгруэнций.

Пусть Р ( N. о ) - класс счетных алгебр с ненулевыми конгруэнциями только конечного индекса (с нетеровыми решетками конгруэнций, со счетными решетками конгруэнций). Очевидно Р с ы с С.

В первом параграфе изучаются позитивные Р-алгебры. Как отмечалось выше, никакая счетная артшова решетка не реализуется в качестве решетки конгруэнций никакой неконструктивной позитивной алгебры. Простейшей полной алгебраической неартиновой решеткой является 1+ш* ( ш* - порядок, двойственный естественному упорядочению множества.натуральных чисел и).

А.И. Мальцевым в [8] доказана конструктивность всякой позитивной конечно-поровденной Р-алгебры. Естественно возник вопрос о существенности свойства конечной порожденное™ в этом результате. Построены примеры конструктивизируемой и неконструктивизируемой Р-алгебр, решетки конгруэнций которых изоморфны 1+ш*, обладающих неконструктивными позитивными нумерациями. Доказано, что характеристическая трансверсаль позитивной р-алгебры либо рекурсивна, либо гипериммунна. Изучено строение Р-алгебр, обладающих неконструктивными позитивными нумерациями.

Основной результат второго параграфа - ответ на вопрос : можно ли в упомянутой теореме А.И. Мальцева заменить условие конечности индексов ненулевых конгруэнций близким, но более общим, условием нетеровости ?

ТЕОРЕМА 4.2.1. Всякая позитивная Р-алгебра эффективно вложима в позитивную конечно-поровденную л-алгебру.

СЛЕДСТВИЕ 4.2.1. Существует неконструктивизируемая позитивно представимая конечно-порожденная 11-алгебра.

В качестве усиления этого следствия построен пример двухсортной л-алгебры с неразрешимой проблемой равенства,

конечно-определенной в конечно-базируемом многообразии.

Третий параграф посвящен изучению некоторых общих свойств С-алгебр.

ТЕОРЕМА 4.3.1. Пусть (81,v) - позитивная С-алгебра. Тогда

1) V - рекурсивно отделимая нумерация;

2) характеристическая трансверсаль нумерации v либо не •иммунна, либо гипериммунна;

3) (91,V) аппроксимируется конструктивными алгебрами. СЛЕДСТВИЕ 4.3.1. Всякая С-алгебра, обладающая неэффек-

' тивно бесконечной позитивной нумерацией является локально-конечной и финитно-аппроксимируемой.

Доказано, что существование конечно-порожденного обогащения позитивной С-алгебры равносильно не иммунности ее характеристической.трансверсали.

Изучен вопрос о числе непозитивных конгруэнций позитивных алгебр. Показано, что для всякого п % ш U {ш} существует позитивная алгебра, имеющая ровно п непозитивных конгруэнций.

Автор выражает глубокую благодарность профессору С.С.Гончарову за постоянное внимание и всестороннюю поддержку при работе над диссертацией.

ЛИТЕРАТУРА

1. Гончаров С.С. Проблема числа неавтоэквивалентных конструк-тивизаций // Алгебра и логика. - 1980. - Т.19, № 6. - С. 621-639.

2. Гончаров С.С. Модели данных и языки их описания // Выч. системы. - 1985. - вып. 107. - С. 52-70.

3. Гончаров С.С. Счетные булевы алгебры. -Новосибирск: Наука, 1988.

4. Ершов Ю.Л. Теория нумераций. - М.: Наука,1977.

5. Ершов Ю.Л. Проблемы разрешимости и конструктивные модели. -М.: Наука, 1980.

6. Кузнецов A.B. О проблемах тождества и функциональной полноты для алгебраических систем // Труды III Beее. матем. съезда. - Москва. -1956. - Т.2. - С.145-146.

7. Мальцев А.И. О гомоморфизмах на конечные группы // Учен, зап. Ивановск. пед. ин-та. - 1958. - Т.18. - С.49-60.

8. Мальцев А.И. Конструктивные алгебры. 1 // Успехи матем.

наук. - 1961. - Т.16., » 3. - С. 3-60.

9. Мальцев А.И. Полно нумерованные множества // Алгебра и логика. - 1963. - Т.2, * 2. - С. 4-29.

Ю. Мальцев А.И. К теории вычислимых семейств объектов // Алгебра и логика. - 1964. - Т.З, * 4. - С. 5-31.

11. Мальцев A.M. Позитивные и негативные нумерации // Докл. АН СССР. - 1965. - Т.103, * 5. - С. 278-280.

12. Морозов А.С. Об одном вопросе Хигмэна // Алгебра и логика. - 1990. - Т.29, * 1." - С. 29-34.

13. Одинцов С.П..Селиванов В.Л. Арифметическая иерархия и идеалы нумерованных булевых алгебр // Сиб. матем. ж. -1989. - Т.30, Л 6. - С. 140-149.

14. Успенский В.А. О вычислимых операциях // Докл. АН СССР.

- 1955. - Т.103, J6 5. - С. 773-776.

15- Успенский В.А. Системы перечислимых множеств и их нумерации // Докл. АН СССР. - 1955.- Т.105, * 6. - С. 1155-1158.

16. Успенский В.А., Сембнов А.Л. Теория алгоритмов: основные открытия и приложения. - М.: Наука, 1987.

17. Baur W. Rekursive Algebren mit Kettenbedingungen // Z. Math. Logilc und Grundl. Math. - 1974. -B.20,* 1. -S.37-46.

18. Bergstra J.A..Tucker J.Y. A characterization of computable data types by means of a finite, eguational specification method // Lect.Not. Сотр. Sci. - 1980. - Ji 85. - P. 76-90. 19- Kamin S. Some definitions for algebraio data type specifications // SIGPLAN Not. - 1979. - V.14, *5. - P. 28-37.

20. McKinsey J.G. The decision problem for some classes of sentences without guantifiers // J.Symbol.Log.- 1943.-V-8.Jfc3. -P.61-76.

21. Nerode A. General topology and partial recursive functio-nals // Talks Cornell Summ.Inst.Symb.Log. - Cornell. - 1957.

- P.247-251.

Работы автора по теме диссертации

22. Касымов Н.Х. О позитивных нумерациях конечно-порожденных алгебр // Тез. докл. VIII Всес. конф. по матем. логике.

- Москва. - 1986. - С.80.

23. Касымов Н.Х. Об алгебрах с финитно-аппроксимируемыми

позитивно представшими обогащениями // Алгебра и логика.

- 1987. - Т.26, JS 6. - С.715-730.

24. Касымов Н.Х. Логические программы без равенства и конструктивные представления // Выч.системы. - 1987. - вып.122. -С. 3-18.

25. Касымов Н.Х. Алгебраическая характеризация простых множеств // Тез. докл. Всес. конф. по прикладной логике.-Новосибирск. - 1988. - С. 105.

26. Касымов Н.Х. О бесконечной модели с финитно-аппроксимируемыми эффективными обогащениями // Тез.докл. IX Всес.конф. по матем. логике. - Ленинград. - 1988. - С. 71.

27. Касымов Н.Х. О неспецифицируемости эффективно представи-мых данных позитивными формулами // ДАН Уз.ССР. - 1989.- •№ 6.

- С. 4-5.

28. Касымов Н.Х. Об одной двойственной задаче теории конструктивных моделей // Выч. системы. - 1989. - вып. 129. - С. 137-143.

29. Касымов Н.Х. О позитивных алгебрах с конгруэнциями конечного индекса // Мевдународная конф. по алгебре. Тез.докл. по теории моделей и алгебраических систем. - Новосибирск. -1989. - С. 57.

30. Касымов Н.Х. Гомоморфизмы позитивных моделей и рекурсивно -перечислимые универсальные определения // ДАН УзССР.- 1990.

- » 3. - С. 4-5.

31. Касымов Н.Х. Критерий эффективной бесконечности позитивных алгебр с нетеровыми решетками конгруэнций // Тез. докл. X Всес. конф.по матем.логике. - Алма - Ата. - 1990. - С.78.

32. Касымов Н.Х. Позитивные модели и универсальные предложения // Выч.системы. - 1990. - вып. 133. - С. 3-13.

33. Касымов Н.Х. Об одном алгебраическом свойстве простых не гиперпростых множеств // ДАН Уз.ССР. - 1991. - Л 3. - С. 3-4.

34. Касымов Н.Х. Позитивные алгебры с конгруэнциями конечного индекса // Алгебра и логика. - 1991. - Т.30,Л 3.- С. 293-305.

35. Касымов Н.Х. О конгруэнциях неэффективно бесконечных алгебр // Мевдународная конф. по алгебре. Тез.докл. по теории моделей и алгебраических систем. - Барнаул. - 1991. - С. 58.

36. Касымов Н.Х. Позитивные алгебры со счетными решетками конгруэнций // Алгебра и логика. - 1992. - Т.31,*1. -С.21-37.

37. Касымов' Н.Х. О гомоморфизмах на негативные алгебры //Алгебра и логика. - 1992. - Т.31, № 2. - G. 132-144.

38. .Касымов Н.Х. Позитивные алгебры с нетеровыми решетками конгруэнций // Сиб. матем. ж. - 1992. - T.33.JÍ2. - С.181-185.

39. Касымов -Н.Х-. О числе Q-конгруэнций позитивных алгебр '// Алгебра и логика. - 1992. - Т.31, * 3. - С. 297-305.

40. Касымов Н.Х. О гомоморфизмах нумерованных алгебр с рекурсивно отделимыми классами // ДАН РУз. - 1992. - J6 6-7.-С.3-4.

41. Касымов Н.Х. О числе конгруэнций алгебр над простыми множествами // Матем. заметки. - 1992. -T.52.Jt 8. -С.150-152.

42. Касымов Н.Х. Критерий фщщтной аппроксимируемости конечно порожденных неэффективно бесконечных алг,ебр //' Тез.докл. XI Межреспуб. конф. по матем. логике.- Казань. - 1992. - С. 70.

43. Касымов Н.Х. О неспецифицируемости эффективно бесконечных абстрактных структур данных тождествами // Выч. системы.

- 1992. - вып:14б. - С.153. •

. 44. Касымов Н.Х. Неконструктивные негативные алгебры с условиями конечности //-Сиб. матем.ж. - 1992. - Т.3'3,.* б: - С. 195-198. .

45. Касымов Н.Х. Совершенные нумерации алгебр //Узб.-матем.ж.

- 1993. - * 2.

46. Касымов Н.Х. Топологические нумерованные алгебры // ДАН ■РУз. - 1993. - * 8. ,

47. Касымов Н.Х. Аксиомы отделимости и разбиения натурального ряда // Сиб. матем. ж.' - 1993. - Т.34, * 3. - С. 81-85.

48. Касымов Н.Х.' Конечно-поровденные и простые алгебры над' негативными эквивалентностями // Международная конф. по ал-, гебре. Тез. докл. - Красноярск: - 1993, - С. 144. .

49. Касымов Н.Х. Нумерованные алгебры с равномерно рекурсивно отделимыми классами // Сиб. матем. ж. - 1993- - Т.34, * 5. С. 85-102. .