Сложность распознавания приближенного вхождения слов на машинах Тьюринга Иванов, Александр Геннадьевич

Короткий опис

Иванов, Александр Геннадьевич.Сложность распознавания приближенного вхождения слов на машинах Тьюринга : диссертация ... кандидата физико-математических наук : 01.01.06. - Москва, 1984. - 118 с. : ил.

Оглавление диссертациикандидат физико-математических наук Иванов, Александр Геннадьевич
стр.
Введение. 2
§1. Основные понятия. 9
§2. Псевдопериодические разложения и почти периодические слова. 16
§3. Некоторые вспомогательные алгоритмы. 23
§4. Алгоритм для разметки почти периодических начал и псевдопериодических разложений начал данного слова в реальное время. 34
§5. Алгоритм реального времени, распознающий приближенное вхождение слов в метрике Хемминга. 62
§6. Распознавание в реальное время приближенного вхождения слов в метриках , П . 81
§7. Задача распознавания приближенного вхождения в метрике £ . 84
§8. Распознавание точного вхождения слов в реальное время. Литература. 114