Вклад участника
2 июня 2012
Обсуждение:PS-полнота языка верных булевых формул с кванторами (TQBF)
Нет описания правки
+288
Обсуждение:Классы RP и coRP
Новая страница: «Обозначение "программа m" меня убивает. Если программа, то все-таки р, m - это МТ. '''then''' на сл...»
1 июня 2012
Обсуждение:PS-полнота языка верных булевых формул с кванторами (TQBF)
Нет описания правки
+327
Обсуждение:Вероятностные вычисления. Вероятностная машина Тьюринга
Нет описания правки
+2
Обсуждение:Вероятностные вычисления. Вероятностная машина Тьюринга
Нет описания правки
+2
Обсуждение:Вероятностные вычисления. Вероятностная машина Тьюринга
Новая страница: «Претензии по сути: 1) вступление; я его не очень поняла; что значит, что "программы получаю...»
14 мая 2012
13 мая 2012
Классы L, NL, coNL. NL-полнота задачи о достижимости
Теорема Иммермана
-5
Классы L, NL, coNL. NL-полнота задачи о достижимости
Теорема Иммермана
+41
Классы L, NL, coNL. NL-полнота задачи о достижимости
Нет описания правки
+423
Классы L, NL, coNL. NL-полнота задачи о достижимости
Нет описания правки
+27
Классы L, NL, coNL. NL-полнота задачи о достижимости
Теорема Иммермана
-100
Классы L, NL, coNL. NL-полнота задачи о достижимости
Теорема Иммермана
+57
Классы L, NL, coNL. NL-полнота задачи о достижимости
Теорема Иммермана
+4464
30 апреля 2012
Обсуждение:Сложностные классы. Вычисления с оракулом
Нет описания правки
+895
Обсуждение:PS-полнота языка верных булевых формул с кванторами (TQBF)
Нет описания правки
+2
Обсуждение:PS-полнота языка верных булевых формул с кванторами (TQBF)
Новая страница: «Претензии по содержанию * Формулировка леммы 2 не совсем корректна. "Для любого L из PS след...»
Классы L, NL, coNL. NL-полнота задачи о достижимости
Теорема Иммермана
+2487
29 апреля 2012
Классы L, NL, coNL. NL-полнота задачи о достижимости
Теорема Иммермана
+592
Классы L, NL, coNL. NL-полнота задачи о достижимости
Новая страница: «{{Определение |definition='''Класс <tex>L</tex>''' — множество языков, разрешимых на детерминированно...»
23 января 2012
Детерминированные автоматы с магазинной памятью
Нет описания правки
-1464
МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность
Нет описания правки
+77
Автоматы с магазинной памятью
Недетерминированный автомат с магазинной памятью
+177
Лемма Огдена
Нет описания правки
+18
Лемма Огдена
Нет описания правки
Примеры неразрешимых задач: однозначность грамматики
Нет описания правки
-3
Примеры неразрешимых задач: однозначность грамматики
Нет описания правки
+137
Удаление бесполезных символов из грамматики
Достижимые и недостижимые нетерминалы
Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора
Нет описания правки
+5
Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора
Нет описания правки
-19
Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора
Нет описания правки
+18
Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора
Нет описания правки
+5
Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора
Нет описания правки
+3
Правоконтекстные грамматики, эквивалентность автоматам
Нет описания правки
-17
22 января 2012
Неукорачивающие и контекстно-зависимые грамматики, эквивалентность
Нет описания правки
+4
Иерархия Хомского формальных грамматик
Распознавание
+8
Иерархия Хомского формальных грамматик
Класс 1
+1
Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками
Примеры
+2
Недетерминированные конечные автоматы
Язык автомата
-11
20 января 2012
29 декабря 2011
20 декабря 2011
19 декабря 2011
18 декабря 2011
Обсуждение:Характеристика перечислимых множеств через вычислимые функции
Нет описания правки
+47
Теория формальных языков
Теория вычислимости
+44
Обсуждение:Характеристика перечислимых множеств через вычислимые функции
Новая страница: «Претензия по сути: отсутствует доказательство 3 <tex>\Rightarrow</tex> 2. По оформлению претензий мн...»
15 декабря 2011
Обсуждение:Разрешимые (рекурсивные) языки
Нет описания правки
-8
Обсуждение:Разрешимые (рекурсивные) языки
Нет описания правки
+3
Обсуждение:Разрешимые (рекурсивные) языки
Нет описания правки
+549
