Уважаемые коллеги,

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

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

Некоторые из базовых работ, которые нам предстоят:

1.Создание библиографии. Надо решить, что является стандартом
библиографического описания. Давайте предложения.

[очень в стиле Андрея --- начать с этого:-]

2.Формирование папки со всеми имеющимися текстовыми файлами.
Установление соответствия между опубликованными работами и
имеющимися текстовыми файлами. Установление соответствий между
русскими текстами и переводами

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

4.Собирание и оцифровка фотографий

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

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

Прошу, по возможности, не посылать тексты в Техе, а переводить
их в ПостСкрипт или ПДФ.

Алексей Семенов 01.04.07

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

Андрей Альбертович Мучник. Темы работ, результаты, библиография

1. Дифференциальные уравнения - Ильяшенко, Сборник

2.Автоматы и регулярные выражения. Теорема Шутценберже

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

3.Прикладная работа в Гипротеатре (Сопрунов)

4.Контекстно-свободные грамматики и степенные ряды

a.Связь алгоритмических и топологических свойств, Труды
   конференции

5.Разрешимые теории

a.Теорема Рабина

b.Теорема Шелаха - Ступа

c.Самовыразимость теории сложения целых чисел

d. новое доказательство Теоремы Кобхэма - Семенова

e.

6.Игровая интерпретация теории алгоритмов

a.ДАН

7.Эффективная сходимость, сложность описания и проблема Поста

a.Конференция Маркова

8.Алгебра и логика сложности

a.Невыделяемость общей информации

b.С Посицельским - Успехи?

c.Конгресс по логике, философии, методологии науки

d.С Семеновым в Дагштуле

e.С Семеновым в Мюнстере

f.С Семеновым в Геттингене

g.Конференция Новикова

h.Конференция Адяна

i.Российско-австрийский симпозиум

j.Сложность в почти периодических последовательность с Семеновым
  и Ушаковым

9.Разные определения случайности

10.Проблема Колмогорова. Комбинаторные и алгоритмические варианты

a.ДАН

b.ППИ

11.Эксперты и предсказания

a.Со швейцарцами (Чернов)

b.Итальянская конференция

c.С Семеновым?

добавлено верещагиным (совместные публикации и список работ от леши чернова):


Колмогоровcкая сложность

Andrej Muchnik, Alexander Shen, Nikolai Vereshchagin, Michael
Vyugin. ``Non-reducible descriptions for conditional Kolmogorov
complexity''. Theory and Applications of Models of Computation,
Third International Conference, TAMC 2006, Beijing, China, May
15-20, 2006, Proceedings. Lecture Notes in Computer Science 3959
Springer 2006, pages 308--317.

  muchnik-tamc2006.pdf -- видимо, гранки из LNCS
  muchnik-tamc2006.zip -- исходные тексты для конференции

 Это вроде как принято к печати в TCS (в расширенном виде, в
 числе авторов также М.Устинов, и имеются исходные тексты этого
 muchnik-tamc2006-tcs.pdf muchnik-tamc2006-tcs.zip

 Предварительная версия была в ECCC, 2004, no. 54.
 muchnik-tamc2006-eccc.pdf muchnik-tamc2006-eccc.ps

An. Muchnik and N. Vereshchagin. ``Shannon Entropy vs. Kolmogorov
Complexity''. Computer Science --- Theory and Applications:
First International Computer Science Symposium in Russia, CSR
2006, St. Petersburg, Russia, June 8-12. 2006. Proceedings.
Editors: Dima Grigoriev, John Harrison, Edward A. Hirsch.
Lecture Notes in Computer Science, vol. 3967 / 2006, pages
281--291.

[shannon-vs-kolmogorov.tex]

A. Chernov, An. Muchnik, A. Romashchenko, A. Shen, and N.
Vereshchagin. Upper semi-lattice of binary strings with the
relation ``x is simple conditional to y''. Theoretical Computer
Science 271, No.1--2, (2002), 69--95.

[Посланный в журнал файл: muchnik-semilat.tex]

[Предварительная версия (без Чернова) была опубликована в
Proceedings of the 14th Annual IEEE Conference on Computational
Complexity, 4--6 May 1999, Atlanta, Georgia, USA. IEEE Computer
Society, 1999. Есть файл: muchnik-semilat-atlanta.pdf]

A. Muchnik and N. Vereshchagin. "Logical operations and
Kolmogorov complexity. II". Proc. of 16th Annual IEEE Conference
on Computational Complexity, Chicago, June 2001, pp. 256--265.

Сложность вычислений

An. Muchnik and N. Vereshchagin. A General Method to Construct
Oracles Realizing Given Relationships between Complexity
Classes. Theoretical computer science 157, No.2, (1996) 227-258.
Extended version: TR-500, University of Rochester.

Разное

1. Мучник,Ан.А.,
   О теореме Шютценберже, касающейся моноидов
   без нетривиальных подгрупп,
   Математическая логика, математическая лингвистика
   и теория алгоритмов, Калинин, 1983,  с.65--68.

2. Muchnik, An.A.
   An application of Semenov's  method to analysis of structure of
   context-free  languages.
   Proceedings  of  Symposium on Semiotical aspects of
   formalization of intellectual activity held in Kutaisi
   (Georgia), Moscow, 1985, pp. 212-214 (in Russian).
   <тезисы>

3. Мучник,Ан.А.,
   Об основных структурах дескриптивной теории алгоритмов,
   Доклады АН СССР, 1985, т.285, N2, с.280--283.

[есть оттиск и сканированный с него файл muchnik-descriptive.djvu,
muchnik-descriptive.pdf]

[Видимо, должен быть английский перевод?]

4. Мучник,Ан.А.,
   Игры на бесконечных деревьях и автоматы с тупиками.
   Новое доказательство разрешимости монадической теории двух следований,
   Семиотика и информатика, 1985, вып.24, с.16--40.
   (перевод: Muchnik,An.A.,
   Games on Infinite Trees and Automata with Dead-Ends.
   A New Proof for the Decidability of the Monadic Second Order Theory
   of Two Successors,
   Bulletin of the European Association for
   Theoretical Computer Science, 1992, vol.48, pp.219--267.)

  [Есть подготовленный в \TeX е русский текст, но только оттиск.
  Может быть, набранный текст из Семиотики? или для какого-то
  переиздания?]

5. Мучник,Ан.А.,
   On the extraction of common information of two words,
   Первый всемирный конгресс Общества математической
   статистики и теории вероятностей имени Бернулли, Тезисы,
   Москва: Наука, 1986, т.1, с.453.
<тезисы>

6.  Мучник,Ан.А.,
    Нижние пределы частот в вычислимых последовательностях
    и релятивизованная априорная вероятность,
    Теория вероятностей и её применения,
    1987, т.32, N3, с. 563--565.

    (перевод: Muchnik,An.A.,
    Lower limits on frequences in computable sequences and
    relativized a priory probability,
    SIAM Theory Probab. Appl.,
    1987, vol.32, pp.513--514.)

Статья, где объясняется, что нижние пределы частот в вычислимых
последовательностях соответствуют $\mathbf{0}'$\д перечислимым
снизу полумерам.
        %
есть файл (скан русского оттиска) muchnik-freq.djvu,
muchnik-freq.pdf

7.  Мучник,Ан.А.,
    Об одном классе полиномиальных систем уравнений, вытекающих из
    формулы полной вероятности, и возможности устранения перебора
    при их решении,
    Проблемы сокращения перебора, Вопросы кибернетики,
    Москва: НСК АН СССР, 1987, вып.???, с.180--194.

8. An. A. Muchnik and L.S. Kost'ukova.
   About THIS and about THAT. Semiotic aspects of
   formalization of intellectual activity.
   All-Union School-Seminar, Borzhomi,
   Thesises, Moscow, 1988, pp. 315-318 (In Russian).
<тезисы, лингвистика>

9.  Мучник,Ан.А.,
    О сильно универсальных сетях конечных автоматов,
    Девятая всесоюзная конференция по математической логике,
    Тезисы, 1988, с.111.

10. Muchnik,An.A.,
    On the inclusion of the class $BPP$ into the class $\Pi_2$,
    The Journal of Symbolic Logic,
    1991, vol.56, no.3, p.1135.

11. Muchnik,An.A., Soprunov,S.F.,
    Decudability of monadic theories of countable structures
    and of their classes,
    The Journal of Symbolic Logic,
    1991, vol.56, no.3, pp.1146--1147.


13. Muchnik,An.A., On common information, Theoretical Computer
    Science, Nov.~1998, vol.207, No.2, pp.319--328.

[есть файл (видимо, из архива журнала), searchable pdf,
muchnik-common-information.pdf, есть оттиск]

14. Muchnik, An.A., Semenov,A.L., Uspensky V.A.,
    Mathematical metaphysics of randomness,
    Theoretical Computer Science,
    Nov. 1998, vol.207, No.2,  pp.263--317.

[есть PDF файл статьи, видимо, из журнала. Searchable.
muchnik-metaphysics.pdf]

15. Мучник,Ан.А., Посицельский,С.Е.,
    Об одном классе перечислимых множеств,
    Успехи математических наук,
    1999, т.54, N3, с.171--172.
<предварительная, см. 22>

16. Мучник Андрей Альбертович,
    Решение некоторых задач теории алгоритмов с использованием
    игровых методов,
    Диссертация кандидата физико-математических наук,
    Москва: МГУ, 2001.
<на правах рукописи>


18. Muchnik, Andrei, Shen, Alexander, Vereshchagin, Nikolai,
    Logical operations and Kolmogorov complexity,
    Abstracts of International conference ``Mathematical Logic,
    Algebra and Set Theory'' dedicated to the 100-th anniversary
    of P. S. Novikov, Moscow, 2001, p.34.
<тезисы>

19. Muchnik, AndreiA., Semenov, AlexeiL.,
    Single intermediate degrees in some classical reducibilities,
    Abstracts of International conference ``Mathematical Logic,
    Algebra and Set Theory'' dedicated to the 100-th anniversary
    of P. S. Novikov, Moscow, 2001, p.33.
<тезисы>

20. Muchnik,An.A., Semenov,A.L.,
    Entropies of finite objects help to define single
    intermediate degrees in some classical reducibilities,
    Proceedings of the International Workshop on
    ``Logic and Complexity in Computer Science'',
    Paris, 2001, pp.195--197.
<тезисы, повтор 19>

21. Muchnik, Andrej A.,
    Conditional complexity and codes,
    Theoretical Computer Science,
    2002, vol.271, nos.1--2, pp.97--109.

[есть электронная копия, searchable pdf, видимо, из журнала;
muchnik-conditional.pdf; есть посланный в журнал исходный текст
muchnik-conditional.tex]

Первоначальная версия: A. Muchnik, A. Semenov, Multi-conditional
descriptions and codes in Kolmogorov complexity, ECCC Report
TR2000-15

[файл из архива: muchnik-semenov-conditional.ps,
                 muchnik-semenov-conditional.pdf]
        %
Есть русский текст (с которого переводился английский для
журнала и нигде не публиковавшийся: muchnik-conditional-rus.tex,
muchnik-conditional-rus.pdf).


22. Muchnik, An. A., Positselsky, S. Ye.,
    Kolmogorov entropy in the context of computability theory,
    Theoretical Computer Science,
    2002, vol.271, nos.1--2, pp.15--35.

[есть searchable pdf: muchnik-posic-eng.pdf, посланный в журнал
текст muchnik-posic-eng.tex]

Первоначальный русский вариант: Андрей А. Мучник, Семен Е. Посицельский,
Колмогоровская энтропия с точки зрения общей теории алгоритмов. Препринт.
М.: Институт новых технологий образования, 1999.

[оттиск в зелёной обложке; видно, что текст готовился в \TeX е,
но есть только совсем предварительный файл начала,
muchnik-posic-rus.tex, muchnik-posic-rus.pdf. Есть ксерокопия
рукописи.]


26. Muchnik,An.A., One application of real-valued interpretation
    of formal power series, Theoretical Computer Science, 2003,
    vol.290, No.3, pp.1931--1946.

Исходный русский текст:

Ан.А.Мучник, Одно применение действительно-значной интерпретации
грамматических рядов. Препринт. М.: Институт новых технологий, 1991.
        %
[по тексту видно, что подготовлен в CW, благодарность Верещагину за помощь,
расширенная версия статьи: Мучник Ан.А., Применение метода Семенова к
анализу структуры контекстно-свободных языков, Тезисы докладов и сообщений
всесоюзной школы-семинара ``Семиотические аспекты формализации интеллектуальной
деятельности. Кутаиси'', с.212--214, Москва, 1985 ]
        %
[GRAM_NUM.TEX файл с текстом неясной степени окончательности;
был когда-то перенесен с macintosh и перекодирован
GRAM_NUM.pdf
--чернов]
        %
Есть файл перевода: An.A.Muchnik,
One application of real-valued interpretation of formal power
series. Prerpint. Institute of New Technologies.
[muchnik-real-valued.pdf, muchnik-real-valued.tex]

27. Muchnik, An.A.,
    The definable criterion for definability in Presburger
    arithmetic and its applications, Theoretical Computer
    Science, 2003, vol.290, No.3, pp.1433--1444.

Первоначальный русский текст:

Ан.А.Мучник, Выразимый критерий выразимости в арифметике Пресбургера
и его применения. Препринт. М.:Институт новых технологий, 1991.
        %
[есть оттиск, видимо, подготовленный в CW, файла нет. Есть
(предварительный?) файл перевода, в том числе \TeX,
muchnik-expression.tex, muchnik-expression.pdf, An.A.Muchnik,
The definable criterion for definability in Presburger
arithmetic and its application, Preprint. Institute of New
Technologies.]

28. Мучник,Ан.А., Семенов,А.Л.,
    О роли закона больших чисел в теории случайности,
    Проблемы передачи информации,
    2003, т.39, N1, сс. 134--165.
    (перевод: Muchnik, An.A., Semenov,A.L.,
    On the Law of Large Numbers in Theory of Randomness,
    Problems of Information Transmission,
    2003, vol.39, N1, pp. 119--147.)

[(Имеется файл muchnik-semenov-random.ps, подготовленный в \TeX е,
исходного файла нет, видимо, для подачи в журнал 
--заменил этот файл своим--чернов)
muchnik-semenov-random-PPI-submitted.ps - текст статьи, 
         представленной в  Проблемы передачи информации
muchnik-semenov-random-PPI-submitted.tex - исходный текст
muchnik-semenov-random-PTI.pdf - окончательный текст перевода на английский
         (получен от Дм. Ногина, как я помню)
muchnik-semenov-random-PTI-submitted.tex - исходный текст перевода
--чернов
]



    А.Л. Семенов, Ан.А. Мучник.
    Об уточнении оценок Колмогорова,
    относящихся к датчикам случайных чисел и
    сложностному определению случайности.
    Доклады АН, 2003, т. 391, N6, с. 738--740.
    (перевод: A.L. Semenov, An.A. Muchnik.
    An Improvement of Kolmogorov's Estimates Related 
    to Random Number Generators
    and a Definition of Randomness in Terms of Complexity.
    Doklady Mathematics, 2003, Vol. 68, No. 1, pp. 132--134.)
[
muchnik-semenov-random-DAN.pdf - окончательный текст статьи в Докладах 
    (получен из редакции)
muchnik-semenov-random-DAN-submitted.tex - исходный текст
muchnik-semenov-random-DAN-remark.tex - примечание при корректуре
muchnik-semenov-random-DAN-eng.txt - ? окончательный текст перевода 
    (вроде бы, получен из редакции)
muchnik-semenov-random-DAN-submitted-eng.tex - исходный текст перевода
muchnik-semenov-random-DAN-remark-eng.tex - перевод примечания при корректуре
--чернов
]


24. Muchnik,An.A., Semenov,A.L.,
    Correlations between randomness of finite sequences and
    stability of the frequences in simple subsequences,
    2-nd Moscow -- Vienna Workshop on Logic and Computation,
    Moscow, 26--27 April, 2002.

[muchnik-semenov-random-abstract-Moscow-Vienna.tex - программа workshop'а +
    резюме доклада, как оно было послано Яворскому 19.04.2002
    исходный вариант слайдов не сохранился - они были отредактированы
    для Logic Colloquium
]


25. Muchnik, An.A., Semenov,A.L.,
    Frequency and universal approaches to randomness of
    finite sequences.
    Logic Colloquium 2002,
    3--9 August 2002, Muenster, Germany.
    The Bulletin of Symbolic Logic, Volume 9, 2003, p. 102.
[
Ссылка на опубликованные тезисы взята со страницы
http://www.math.ucla.edu/~asl/bsl/09-toc.htm
файл http://www.math.ucla.edu/~asl/bsl/0901/0901-006.ps
muchnik-semenov-random-abstract-Muenster.ps - вырезанная страница с тезисами
muchnik-semenov-random-abstract-Muenster.tex - исходный текст, посланный на конференцию
muchnik-semenov-random-slides-Muenster.zip - слайды доклада (tex-файлы)
]

    An.A. Muchnik, A.L. Semenov
    40 years of the origin of Kolmogorov randomness theory,
    International conference "Kolmogorov and Contemporary Mathematics",
    June 16 - 21, 2003, Moscow, Russia

[доклад в расписании: http://kolmogorov-100.mi.ras.ru/sched4.htm#JUNE_20_FRIDAY
muchnik-semenov-random-abstract-Kolmogorov100.ps - окончательный (?) 
    текст тезисов по-английски
muchnik-semenov-random-slides-Kolmogorov100.ps - слайды доклада
muchnik-semenov-random-unpublished.tex - ещё один текст на эту тему, 
видимо, неопубликованный; я не разбирал, что там нового по сравнению с большой 
статьей в ППИ; как я помню, планировалось что-то опубликовать после конференции,
но не знаю, чем это кончилось; 
этот файл у меня имеет дату 1.11.2003 (непосредственно перед моим отъездом в Швейцарию);
вероятно, кто-то продолжал работу над этим текстом. Кто?
]





Ещё найдено (из DBLP)

Bruno Durand, Andrei A. Muchnik, Maxim Ushakov, Nikolai
K.~Vereshchagin, Ecological Turing machines. Automata, Languages
and Programming. 31st International Colloquium, ICALP 2004.
Turku, Finland. July 12--16, 2004. Proceedings. Lecture Notes in
Computer Science, 3142. Springer, 2004. ISBN 3-540-22849-7.

[Eco-ICALP-vere.tex]

Richard Beigel, Harry Buhrman, Peter A. Feier, Lance Fortnow,
Piotr Grabowski, Luc Longpr\'e, Andrei Muchnik, Frank Stephan,
Leen Torenvliet, Enumerations of the Kolmogorov function,
ECCC, 2004 (015).

[muchnik-beigel.ps, muchnik-beigel.pdf]

Andrei A. Muchnik, Alexei L. Semenov, Maxim Ushakov, Almost
periodic sequences. \emph{Theoretical Computer Science}, 304,
v.1--3, July 2003

[в архиве журнала есть электронная версия]
Есть исходный текст и pdf-файл явно предварительного варианта
(muchnik-semenov-ushakov.pdf, muchnik-semenov-ushakov.zip).

-----

Текст диссертации (предварительный, без оглавления и др.) в виде
pdf: muchnik-disser.pdf. Ещё более предварительный (видимо --
там нечто пропущено в сравнении с pdf) исходный текст:
muchnik-disser.zip

Есть рукопись без заглавия, начинающаяся словами: ``ТЕОРЕМА.
Двумерная модель действительных алгебраических чисел со
сложением и умножением несамовыразима.'' [muchnik-nesamov.tex,
muchnik-nesamov.pdf]

Доклад в Дагштуле:
Alexei Semenov, Andrej Muchnik, Cryptography in the Context of
Kolmogorov Entropy (слайды)
        %
[muchnik-crypt.ps muchnik-crypt.pdf]

An. Muchnik
On mutual information of a binary word and its entropy,
неопубликованный текст, подготовлен Лёшей Черновым
        %
[muchnik-on-mutual.tex, muchnik-on-mutual.pdf]
        %
Русский текст (видимо, именно он переводился):
[muchnik-on-mutual-rus.tex, muchnik-on-mutual-rus.pdf]


Ан.Мучник, О сложности перехода от перечислимого задания конечной
структуры к её явному заданию,
неопубликованный текст на русском языке
        %
[muchnik-o-slozhnosti.tex, muchnik-o-slozhnosti.pdf]

Текст (неопубликованный) без заглавия о супермартингалах
на русском языке,
[muchnik-supermart.tex, muchnik-supermart.pdf]

Есть ещё написанный самим Андреем обзор его работ
(auto-bio.txt), сначала английский, потом русский (с указанием
планов), довольно давний, видимо
bibliogr-diss.pdf - список работ, поданный с диссертационный совет в 2001 году

Последний рассказ Андрея записан в книге о колмогоровской
сложности, appl-llll.tex (глава о приложениях колмогоровской
сложности, запрещённые подпоследовательности)



-----
Следующие 6 файлов в TeX были в мае 2002 перенесены с macintosh 
(с возможными потерями при перекодировании), 
первые 3 описаны Юрой Притыкиным:


1. ``Тупиковое'' решение проблемы пустоты и проблемы регуляризации
автоматов на бесконечных деревьях. 8 с.
Степень его готовности пока сложно оценить. Имеются две теоремы с
доказательствами. Там написано, что это продолжение работы
Ан.А.Мучник. Игры на бесконечных  деревьях  и  автоматы  с
тупиками. Новое доказательство  разрешимости  монадической  теории
двух следований//Семиотика и информатика, 1985, ${\rm N}^{\circ}$ 24, стр.16-40.

[TREE_NUM.TEX, TREE_NUM.pdf]

2. Есть неозаглавленный текст про finite transducers по мотивам Вебера,
22 с. Этот текст мы с Андреем Альбертовичем обсуждали, я его читал и
разбирался в свое время, он в довольно хорошем состоянии.

[TRANSDUC.TEX, TRANSDUC.pdf]

3. Есть неозаглавленный текст про монадические теории на деревьях, 10
с. Одна теорема с доказательством. Степень готовности не ясна.
Начинается он с параграфа 4, очень похоже, что это не вставленный в
диссертацию параграф, потому что 1 глава диссертации заканчивается 3-м
параграфом, и все очень сходится.

[MONAD_TH.TEX, MONAD_TH.pdf,
tree_str.tex, tree_str.pdf - англ. перевод, чей - неизвестно]

4. Неозаглавленный текст, начинается
"Напомним, что автоматной игрой с двумя игроками..."
Содержит две теоремы: 
 I. Любая автоматная игра является детерминированной, и по ней эффективно
    определяется, у какого игрока есть выигрышная стратегия.
II. Существует алгоритм, который по любой автоматной игре $G$ 
решает вопрос о существовании минимального числа $n$ такого, 
что в игре $G(n)$ второй игрок имеет выигрышную  стратегию и, 
если оно существует, находит это число. 
(В игре G(n) первый игрок указывает свои следующие n ходов, то есть
на первом шаге первый игрок объявляет свои первые (n+1) ходов, второй ---
свой первый ход, а на каждом следующем шаге каждый игрок добавляет 1 ход.)

[AUT_GAME.TEX, AUT_GAME.pdf]

5. Неозаглавленный текст, разбитый на параграфы:
"Графовые грамматики и машины: случай ограниченного ветвления",
"Связь с решетками", 
"Графовые машины: случай неограниченного ветвления", "Гиперграфы".
Много ссылок на отсутствующий список литературы.
Тематика текста связана со следующей теоремой Слисенко:
"Существует  алгоритм,  который  по  размеченному связному графу $G$
и  грамматике  выясняет, выводим  ли $G$  в  этой грамматике, 
и если выводим, строит его  вывод.  При  фиксированной грамматике $\Gamma$ 
время работы этого алгоритма полиномиально зависит от размера $G$."
Есть ссылки на частные сообщения Горбунова.
14 теорем, 27 стр.

[GRAPH_GR.TEX, GRAPH_GR.pdf]

6. "Детерминизация ординальных автоматов", 15 стр., одна теорема:
Для  любого  ординального  автомата  $\cal A$    существует
детерминированный ординальный автомат  $\cal B$, $\rho $-эквивалентный  $\cal A$   для
всех счетных ординалов $\rho $. Автомат $\cal B$  можно построить по  $\cal A$,  причем
количество состояний $\cal B$ есть $2^{2^{O(N)}}$, где $N$ ---  количество  состояний
$\cal A$.

[ORD_AUT.TEX, ORD_AUT.pdf]



