Brief summary of my research activity. When I was student I studied the applications of finite automata to decidability of monadic theories. Famous Rabin's proof of decidability of monadic theory of infinite tree used transfinite induction and Rabin stated the problem to prove the same theorem with using weaker means. It was done by me and independently (and in another way) by Gurevich and Harington. My proof was published in Bulletin of the European Association for Theoretical Computer Science. Shelah and Stupp generalized the Rabin's theorem for trees of infinite branching. My method enables to add to Shelah-Stupp decidability result relations which put connections between different levels of tree. I investigated also complexity of finite automata which correspond to monadic formulas. The next my work is devoted to simplification of the proof of Schutzenberger of characterization of monoids without nontrivial subgroups. The next my work is devoted to context-free grammars. I proved the effective separability of two invariant properties (of kind of linearity and nonlinearity) of context-free languages. The general theory of algorithms has a famous strangeness. At the beginning of constructing of this theory we have to introduce some formal definition of algorithm (such as Turing machine) which later actually isn't used. I presented a new machine-free construction of the theory of algorithms founded on game approach. In addition the formal definition of the theory of algorithms lets formally prove impossibility of something (for example, that we can't eliminate additive constant in Kolmogorov-Solomonoff definition of complexity of finite objects). The next my work is connected with the mentioned in the previous paragraph Kolmogorov complexity. I gave upper and lower estimates on possibility of extraction of common information of two finite objects as a third object. Iterative arrays enable to consider strong notion of universal algorithm, when interpreted algorithms work in parallel way. I studied how it reflects on the time of their work. In 1948 Tarski stated the question: "Is the notion of definability in some language definable in the same language?" For most languages the answer is negative. For some languages we have independent result. I found the first nontrivial positive example, namely Presburger arithmetic. Last time one of my main topics is the algorithmic probability theory. It throws a new light on the notion of randomness (which is connected with many paradoxes in its classical interpretation). In Kolmogorov's paper (published in the Russian journal "Problemy Peredachi Informacii" 1969, v.5, No 3, pp.3-7) he considers correlations between frequency and complexity approaches. My result related to this question was published in the Russian journal "Uspehi Matematicheskih Nauk" 1990, v.45, No 1, pp.151-154 (it disproves Kolmogorov's clime from his paper mentioned above). End of the summary. Список научных трудов Андрея Альбертовича Мучника. 1. О теореме Шютценберже, касающейся моноидов без нетривиальных подгрупп. 1983. Упрощение доказательства. 2. Игры на бесконечных деревьях и автоматы с тупиками. Новое доказательство разрешимости монадической теории двух следований. 1985. Придумано в 1979. В отличие от доказательства Рабина не используется трансфинитная индукция. Games on Infinite Trees and Automata with Dead-Ends. A New Proof for the Decidability of the Monadic Second Order Theory of Two Successors. 1992. Перевод. Гуревич и Харрингтон - 1982. Устранение их пробелов: Яхнис и Яхнис - 1994. Неопубликовано: древесная надстройка структуры - конечные последовательности элементов структуры, отношения надстройки - {1} отношения структуры на последних элементах братьев и {2} равенство последних элементов отца и сына. (Добавление отношения равенства несоседних элементов последовательности делает монадическую теорию древесной надстройки натурального ряда со штрихом неразрешимой, в то время как монадическая теория самой структуры натурального ряда со штрихом, как известно, разрешима.) Теорема: монадическая теория древесной надстройки сводится к монадической теории самой структуры. Шелах и Ступп доказали то же для древесных структур без отношения {2}, что существенно обедняет язык. 3. Применение метода Семёнова к анализу структуры контекстно-свободных языков. 1985. Одно применение действительно-значной интерпретации грамматических рядов. Препринт. 1991. Алгоритмическое отделение линейных языков от сильно нелинейных языков(языков, а не грамматик!). 4. Об основных структурах дескриптивной теории алгоритмов. 1985. Игровая интерпретация теории алгоритмов и релятивизуемые утверждения. 5. Я участвовал в обсуждении проблемы неарифметичности предикатной логики доказуемости. 6. On the extraction of common information of two words. 1986. On common information. 1998. Два метода построения пар объектов с невыделяемой общей информацией. (совместно с А.Е.Ромащенко, А.Х.Шенем, Н.К.Верещагиным) Upper semi-lattice of binary strings with the relation "x is simple conditional to y". 1999. Разные геометрические примеры, метод случайного блуждания по графам. Предстоит опубликовать: самый сильный пример, метод вероятностного построения функций со специальными свойствами. 7. Нижние пределы частот в вычислимых последовательностях и релятивизованная априорная вероятность. 1987. Н.К.Верещагин доказал, что верхний предел условной энтропии (при условии, стремемящемся к бесконечности) равен энтропии с оракулом 0'. 1999. 8. Об одном классе полиномиальных систем уравнений, вытекающих из формулы полной вероятности, и возможности устранения перебора при их решении. 1987. 9. О сильно универсальных сетях конечных автоматов. 1988. 10. On the inclusion of the class BPP into the class П_2. 1991. Упрощение результата Гача. 11.(совместно с С.Ф. Сопруновым) Decidability of monadic theories of countable structures and of their classes. 1991. Существует одноместный предикат на двоичном дереве, который имеет разрешимую слабо-монадическую теорию, но неразрешимую монадическую теорию (в языке с операциями следования). Наоборот не бывает, так как конечность выразима в монадической теории двоичного дерева. Из детерминизуемости автоматов на сверхсловах следует, что монадическая теория одноместного предиката на натуральном ряде со штрихом сводится к слабо-монадической теории. 12. Выразимый критерий выразимости в арифметике Пресбургера и его применения. Препринт. 1991. Вопрос о существовании "самовыразимого" языка поставлен Тарским в 1948. Было известно, что класс одноместных предикатов, выразимых в неразрешимой элементарной теории сложения и умножения натуральных чисел, не выразим в этой теории. Я доказал, что для каждого n класс n-местных предикатов, выразимых в разрешимой элементарной теории сложения натуральных чисел, выразим в этой теории (построение эффективно по n). В другой разрешимой теории сложения и умножения алгебраических чисел класс выразимых одноместных предикатов выразим, а класс выразимых двуместных предикатов не выразим. Выразимость выразимости в арифметике сложения позволила существенно упростить доказательства следующих двух теорем Семёнова. Хорошо известно, что множества n-ок натуральных чисел, выразимые в арифметике сложения, распознаются конечным автоматом при записи в p-ичной системе счисления для p>1 (автомат строится эффективно по арифметической формуле, n и p). Семёнов доказал, что по автомату, распознающему множество n-ок натуральных чисел в p-ичной системе счисления, можно узнать, выразимо ли это множество в арифметике сложения (в случае выразимости формула строится эффективно). Если (log p)/(log q) - иррационально, то множества n-ок натуральных чисел, автоматно распознаваемые при записи и в p-ичной и в q-ичной системах счисления, выразимы в арифметике сложения. 13. (совместно с Н.К. Верещагиным) A general method to construct oracles realizing given relationships between complexity classes. 1994. 14. (совместно с А.Л.Семёновым и В.А.Успенским) Mathematical metaphysics of randomness. 1998. Сравнение сложностного, игрового и частотного подходов к определению случайности бесконечной двоичной последовательности. Колмогоров доказал, что для монотонных правил выбора существует последовательность с логарифмическим ростом сложности начал, в которой при каждом вычислимом правиле выбора частота обеих цифр стремится к 1/2. То же самое без доказательства утверждается в публикации Колмогорова для немонотонных правил выбора. Эта гипотеза опровергнута. Рассмотрение мер, медленно стремящихся к равномерной, показывает, что частотный подход всё-таки не эквивалентен сложностному. Мы даём анализ игрового подхода, который гораздо ближе к сложностному, чем частотный. Впрочем, проблема эквивалентности игрового подхода сложностному остаётся открытой (Ли и Витаньи интересовались в 1999, не решена ли она). Исследуется вопрос о существовании универсальных выигрывающих стратегий. Аналоги основных понятий статьи изучаются для конечных последовательностей. 15. (совместно с С.Е.Посицельским) Об одном классе перечислимых множеств. 1999. Доказано, что r-отделимые множества образуют решётку и что все r-отделимые множества не полны относительно ограниченной сводимости по Тьюрингу. В частности, неполнота простых множеств Поста имеет место при ограниченном количестве обращений к оракулу даже без требования одновременности этих обращений (это требование есть для табличной сводимости). Список научных трудов Горбунова Константина Юрьевича. 1. Об одной алгоритмической проблеме математической лингвистики. Тезисы. 1988. Не существует перечислимого семейства контекстно-свободных грамматик, порождающего класс однозначных языков. 1991. Решение проблемы, поставленной в моей работе из [3]. 2. Контекстно-свободная выводимость графов, не реализующих плоскую решётку. 1991. (совместно с R.Diestel, T.Jensen, C.Thomassen) Highly connected sets and the excluded grid theorem. 1999. Основной результат состоит в оценке древесной ширины графа через размер квадратной решётки, которую граф не реализует. Горбунов получил экспоненциальную верхнюю оценку (известная оценка была неэлементарной, нижняя оценка неизвестна) и линейную верхнюю оценку для плоских графов (известная оценка была квадратичной). Работа начиналась с обобщения метода Слисенко. Это обобщение опубликовано в 1999 другими (Курсель, Маковсий, Ротикс). 3. On a complexity of the formula ((A or B) implies C). 1998. Предстоит опубликовать. 1. Беннет, Гач, Ли, Витаньи, Цурек доказали, что сложность минимальной программы, переводящей x в y и y в x, равна максимуму сложностей минимальной программы, переводящей x в y, и минимальной программы, переводящей y в x. Горбунов доказал в [3], что сложность минимальной программы, переводящей x в z и y в z, бывает равна сумме сложностей минимальной программы, переводящей x в z, и минимальной программы, переводящей y в z. Но сложность x,y,z в примере Горбунова экспоненциальна относительно сложности минимальных программ. Я доказал, что с точностью до логарифма сложности z сумма может быть заменена на максимум (при этом сложность x,y может быть любой). Причём, минимальная программа, переводящая x в z и y в z, всегда может быть выделена из z. С другой стороны, минимальная программа, одновременно переводящая x в z и y в z, бывает независима от пары минимальных программ, переводящих по- отдельности x в z и y в z. Наоборот, минимальная программа, одновременно переводящая x в y и y в x, всегда имеет большую общую информацию с парой минимальных программ по-отдельности переводящих x в y и y в x. Дана точная оценка на мощность универсального множества кодов для получения одного объекта из разных условий. 2. (совместно с М.В.Вьюгиным) Полное решение следующей проблемы. Для каких чисел a,b выполнено, что каждому объекту x можно сопоставить такой объект y, чтобы было K(x|y)=a, K(y|x)=b? Если ab, то y существует не для каждого x. 3. Хорошо известно, что надграфик функции энтропии всегда является слабо- таблично полным множеством. Куммер доказал, что надграфик простой энтропии всегда является таблично полным. Мы с С.Е.Посицельским доказали, что надграфики префиксной энтропии бывают и полными и неполными относительно табличной сводимости. Я доказал, что надграфик условной энтропии всегда является m-полным. Надграфики функций простой и префиксной энтропии однозначно задают две несравнимые перечислимые степени относительно ограниченной сводимости по Тьюрингу (то же выполнено для ограниченной слабо-табличной сводимости). Это первый естественный пример промежуточной перечислимой степени. Для ограниченной табличной сводимости надграфики простой энтропии бывают несранимы друг с другом, и надграфики префиксной энтропии бывают несранимы друг с другом. 4. Одномерная почти-периодичность. (Удобнее определение допускающее "предпериоды".) Детерминированный конечный преобразователь (автомат, заменяющий буквы на любые слова) переводит почти-периодическую последовательность в почти-периодическую последовательность. При этом сохраняется эффективность задания. Недетерминированный преобразователь можно униформизовать недетерминированным преобразователем, который эффективно находится. Недетерминированный преобразователь, получающий на вход почти- периодическую последовательность, можно униформизовать детерминированным преобразователем, который эффективно находится (и зависит от входа). Если входная последовательность не почти-периодична, то детерминированная униформизация бывает невозможна. Универсальный метод построения почти-периодических последовательностей. Важные примеры почти-периодических последовательностей в топологических и метрических компактах, на многомерном торе. (Эффективная) почти-периодичность многомерной последовательности не следует из (эффективной) почти-периодичности всех её собственных проекций. У почти-периодической последовательности начало длины n имеет дефект случайности больше cn для подходящей костанты c. Для каждой константы c существует почти-периодическая последовательность, у которой дефект случайности n-ого начала меньше cn. 5. Разные оценки для конечных автоматов и преобразователей.