WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 ||

A B C D A B C D A B A B C D A B A B C D Понятие разреженной периодичности вызывает следующие важные вопросы: (1) Как перечислить все разреженные периоды (2) Каждое ли слово имеет единственный примитивный разреженный период (3) Как найти все разреженные периоды минимального размера (4) Сколько разреженных периодов может иметь слово длины n (5) Каково отношение между примитивным классическим периодом и примитивным разреженным периодом -10В разделе 5.1 определяется частичный порядок на разреженных периодах. Показано, что, в отличие от классического случая [8], у текста может оказаться несколько примитивных разреженных периодов. Представлен пример (24 буквы), обладающий двумя независимыми примитивными разреженными периодами. Таким образом, получено опровержение гипотезы Теро Харью об общем подразбиении [11].

В подразделе 5.2.1 установлена связь между разреженными периодами слова в однобуквенном алфавите и факторизациями его длины.

Теорема 5.2.1. Существует биективное соответствие между разреженными периодами унарного слова длины n и упорядоченными разложениями n = n1·... ·nk, где n2,..., nk 2.

В подразделе 5.2.2 доказана теорема о связи примитивных разреженных периодов некоторого текста T с его классическим примитивным периодом.

Теорема 5.2.2. Любой примитивный разреженный период Q слова T является также разреженным периодом для классического примитивного периода T.

Из этого свойства следует, что разреженная периодичность живет “внутри” классического примитивного периода. Доказательство основано на расширенном алгоритме Евклида.

Наконец, в подразделе 5.2.3 представлен алгоритм для нахождения (всех) разреженных периодов минимального размера для данного текста.

Время работы алгоритма составляет n1+o(1) шагов.

Список литературы [1] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи // Пер. с англ. Москва, Мир, 1982.

[2] Шур А.М., Гамзова Ю.В. Частичные слова и свойство взаимодействия периодов // Известия РАН. Серия математическая, 2004, 68:2, 191–214.

-11[3] Amir A., Benson G., Farach M. Let sleeping files lie: Pattern matching in Z-compressed files // SODA’94, 1994.

[4] Berman P., Karpinski M., Larmore L., Plandowski W., and Rytter W. On the complexity of pattern matching for highly compressed two-dimensional texts // Journal of Computer and Systems Science, 65(2):332–350, 2002.

[5] Blanchet-Sadri F. Periodicity on partial words // Computers and Mathematics with Applications, 47(1):71–82, 2004.

[6] Boasson L., Berstel J. Partial words and a theorem of Fine and Wilf // Theoretical Computer Science, 218(1):135–141, 1999.

[7] Farach M., Thorup M. String matching in Lempel-Ziv compressed strings // STOC ’95, pages 703–712, ACM Press, 1995.

[8] Fine N., Wilf H. Uniqueness theorems for periodic functions // Proc.

Amer. Math. Soc., 16:109–114, 1965.

[9] G asieniec L., Karpinski M., Plandowski W., and Rytter W. Efficient algorithms for Lempel-Ziv encoding (extended abstract) // SWAT’96, LNCS 1097, pages 392–403, Springer-Verlag, 1996.

[10] Genest B., Muscholl A. Pattern matching and membership for hierarchical message sequence charts // LATIN’02, LNCS 2286, pages 326–340, Springer-Verlag, 2002.

[11] Harju T. Defect theorem // Lecture notes of “Combinatorics of words” Tarragona course, 2002/2003.

[12] Hirao M., Shinohara A., Takeda M., and Arikawa S. Fully compressed pattern matching algorithm for balanced straight-line programs // SPIRE’00, pages 132–138, IEEE Computer Society, 2000.

[13] Krkkinen J., Navarro G., and Ukkonen E. Approximate string matching over Ziv-Lempel compressed text //CPM’00, LNCS 1848, pages 195–209, Springer-Verlag, 2000.

-12[14] Karpinski M., Rytter W., and Shinohara A. Pattern-matching for strings with short descriptions // CPM’95, LNCS 937, pages 205–214, SpringerVerlag, 1995.

[15] Lasota S., Rytter W. Faster algorithm for bisimulation equivalence of normed context-free processes // MFCS’06, LNCS 4162, pages 646–657, Springer-Verlag, 2006.

[16] Lohrey M. Word problems on compressed word // ICALP’04), LNCS 3142, pages 906–918, Springer-Verlag, 2004.

[17] Miyazaki M., Shinohara A., and Takeda M. An improved pattern matching algorithm for strings in terms of straight line programs // CPM ’97, LNCS 1264, pages 1–11, Springer-Verlag, 1997.

[18] Navarro G., Raffinot M. A general practical approach to pattern matching over Ziv-Lempel compressed text // CPM’99, LNCS 1645, pages 14–36, Springer-Verlag, 1999.

[19] Plandowski W. Testing equivalence of morphisms on context-free languages // ESA’94, LNCS 855, pages 460–470, Springer-Verlag, 1994.

[20] Plandowski W. Satisfiability of word equations with constants is in PSPACE // J. ACM, 51(3):483–496, 2004.

[21] Rytter W. Application of Lempel-Ziv factorization to the approximation of grammar-based compression // Theoretical Computer Science, 302(1– 3):211–222, 2003.

[22] Ziv J., Lempel A. A universal algorithm for sequential data compression // IEEE Transactions on Information Theory, 23(3):337–343, 1977.

-13ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ [23] Карьюмяки Ю., Лифшиц Ю.М. Разреженная периодичность // Препринт ПОМИ 22/06, 2006.

[24] Лифшиц Ю.М. Алгоритмические свойства сжатых текстов // Препринт ПОМИ 23/06, 2006.

[25] Лифшиц Ю.М. Обработка сжатых текстов // Материалы XVI Международной школы-семинара “Синтез и сложность управляющих систем”, стр. 64–68, Изд-во механико-математического факультета МГУ, 2006.

[26] Cgielski P., Guessarian I., Lifshits Y., and Matiyasevich Y. Window subsequence problems for compressed texts // CSR’06, LNCS 3967, pages 127–136, Springer-Verlag, 2006.

[27] Lifshits Y., Lohrey M. Querying and embedding compressed texts // MFCS’06, LNCS 4162, pages 681–692, Springer-Verlag, 2006.

Pages:     | 1 ||



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.