Сложность распознавания приближенного вхождения слов на машинах Тьюринга тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

стр.

Введение. 2

§1. Основные понятия. 9

§2. Псевдопериодические разложения и почти периодические слова. 16

§3. Некоторые вспомогательные алгоритмы. 23

§4. Алгоритм для разметки почти периодических начал и псевдопериодических разложений начал данного слова в реальное время. 34

§5. Алгоритм реального времени, распознающий приближенное вхождение слов в метрике Хемминга. 62

§6. Распознавание в реальное время приближенного вхождения слов в метриках , П . 81

§7. Задача распознавания приближенного вхождения в метрике £ . 84

§8. Распознавание точного вхождения слов в реальное время. Литература. 114

Вычисление функции V при котором алгоритм последовательно читает входное слово и при этом выдает значение ^ на Л -буквенном начале слова до того, как будет прочитана + 1 -ая буква слова, называется вычислением в реальное время, если время работы (число шагов) алгоритма с момента прочтения Л -ой буквы до момента прочтения п * £ -ой (называемое замедлениемданного алгоритма на префиксе входного слова длины и ) ограничено некоторой константой, не зависящей от входного слова.

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

Тем самым, в классе задач, решаемых за линейное время, целесообразно выделить подкласс задач, решаемых "предельно быстро", т.е. в реальное время (1ыЗ). Тем более, что во многих прикладных задачах требуются алгоритмы, работающие в темпе поступления информации. К этим задачам относятся задачи обработки информации, задачи управления, распознавания образов.

Применительно к задаче распознавания приближенного вхождения мы интересуемся вычислением такой функции & значение которой на словах V и I/ есть I дли 0 в зависимости от того, существует ли в слове ^Г подслово, которое в рассматриваемой метрике отличается от слова V не более, чем на заданную величинуПодробное определение расстояний между словами в метриках Хемминга, £ и £ (п £ /V ) а также определение понятия реального времени приведено в §1.

1. Адян С.И. Проблема Бернсайда и тождества в группах. - М.: Нау-ка, 1975.

2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

3. Барздинь Я.М. Сложность распознавания симметрии на машинахТьюринга. Пробл. кибернет., 1965, )£15, с.249-252.

4. Житков Г.Н. Некоторые методы автоматической классификацииобзор . В кн.: Структурные методы опознавания и автоматического- чтения. М.; ВИНИТИ, 1970, с.88-90.

5. Иванов А.Г. Распознавание вхождений слов. Шестая Всесоюзнаяконференция по матем. логике. Тезисы докладов. -Тбилиси, 1982, с.71.

6. Иванов А.Г. Распознавание приближенного вхождения слов на машинеТьюринга в реальное время. Изв. АН СССР, сер. матем., 1984,,т.48, №3, с.520-568.

7. Марков Ал.А. Введение в теорию кодирования. М.: Наука, 1982.

8. Матиясевич 10.В. 0 распознавании в реальное время отношениявхождения. Зап. научн. семинаров Ленингр. отд. Матем. ин-та АН СССР, 1971, т.20, с.104-114.

9. Рабин М.0. Вычисления в реальное время. В кн.: Проблемы математической логики. М.: Мир, 1970, с.156-167.

10. Розенберг А.Л. Языки, распознаваемые в реальное время.В кн.: Проблемы математической логики. М.: Мир, . ' 1970, с.168-193.

11. Слисенко А.0. Сложностные задачи теории вычислений. УМН,1981, т.36, вып.6 222 , с.21-103.

12. Слисенко А.0. Распознавание предиката вхождения в реальноевремя. Препринт ЛОМИ Р-7-77, Ленинград, 1977, 24с.

13. Слисенко А.О. Нахождение в реальное время всех периодичностейв слове. ДАН СССР, 1980, т.251, Щ, с.48-51.

14. Слисенко А.О. Поиск периодичностей и идентификация подсловв реальное время. Зап. научн. семинаров Ленингр. отд. Матем. ин-та АН СССР, 1981, т.105, с.62-173.

15. Фрейвальд Р.В. Сложность распознавания симметрии на машинахТьюринга со входом. Алгебра и логика, 1965, т.4, Ж, с.46-58.

16. Фрейдзон Р.И. Характеризация сложности рекурсивных предикатов,не зависящая от стандартизации понятия алгорифма. -Зап. научн. семинаров Ленингр. отд. Матем. ин-та АН СССР, 1968, т.8, с.225-233.

17. Фрейдзон Р.И. Об одной характеристике сложности рекурсивныхпредикатов. Труды Матем. ин-та им. В.А. Стеклова, 1970, т.1ГЗ, с.79-101.

18. Apostolico A., Preparata P.P. Optimal off-line detection ofrepetition in a string. Theor. Comput. Sci., 1983, vol.22, U°3, p.297-316.

19. Boyer R.S., Moore J.S. A fast string searching algorithm.Commun. ACM, 1977, vol.20, №10, p.762-772.

20. Pelsenstein J., Sawyer S., Kochin R. An efficient method formatching nucleic acid sequences. Nucleic Acids Research, 1982, vol.10, №1, p.133-140.

21. Fisher P.С., Meyer A.R. , Rosenberg A.L. Real-time simulation of multihead tape units. J. Assoc. Comput. Mach., 1972, vol.19, №4j p.590-607.

22. Fisher M.J., Paterson M.S. String-matching and other products.1.: Complexity Comput. (SIAM-AMS Proc., vol.7) Providence R.I., 1974, p.113-125.

23. Galil Z. Real-time algorithms for string-matching and palindrome recognition. Proc. 8th Annu. ACM Symp. Theory Comput., Hershey, Pennsylvania, 1976, p.161-173.

24. Galil Z., Seiferas J. Recognising certain repetitions andreversals within strings. IEEE 17th Annu. Symp. Found. Comput. Sci., Houston, Texas, p.236-252.

25. Galil Z., Seiferas J. Real-time recognition of substring repetition and reversal. Math. Syst. Theory, 1977, vol.11, p.111-146.

26. Galil Z., Seiferas J. Saving space in fast string-matching.

27. EE 18th Annu. Symp. Found. Comput. Sci., Providence, Rhode Island, 1977, p.179-188. (also: SIAM J. Comput., 1980, vol.9, №2, p.417-438.)

28. Galil Z. String matching in real time. J. Assoc. Comput.Mach., 1981, vol.28, №1, p.134-149

29. Galil Z. On improving the worst case running time of theBoyer-Moore string matching algorithm. Lect. Hotes Comput. Sci., 1978, vol.62, p.241-250.

30. Galil Z., Seiferas J. Linear-time string-matching using onlya fixed number of local storage locations. Theor. Comput. Sci., 1981, vol.13, p.331-336.

31. Galil Z., Seiferas J. Time-Space-Optimal string matching.J. Comput. and Syst. Sci., 1983, vol.26, №3, p.280-294.

32. Guibas L.J., Odlysco A.M. A new proof of the linearity of theBoyer-Moore string searching algorithm. IEEE 18th Annu. Symp. Pound. Comput. Sci., Providence, Rhode Island, 1977, p.189-195.

33. Knuth D.E., Morris J.H., Pratt V.R. Past pattern matching instrings. SIAM J. Comput., 1977, vol.6, №2, p. 323-350.

34. McCreight E.M. A space-economical suffix tree constructionalgorithm. J. Assoc. Comput. Mach., 1976, vol.23, №2, p.262-272.

35. Hoffmann C.M., O'Donnell M.J. Pattern matching in trees.J. Assoc. Comput. Mach., 1982,' vol.29, №1, p.68-95

36. Weiner P. Linear pattern matching algorithm. IEEE 14th Annu.Symp. Switch, and Automata Theory, Ioma, 1973, p.1-11.