Инд. авторы: Медведева Ю.С.
Заглавие: Быстрая нумерация слов, порождаемых грамматиками Дика
Библ. ссылка: Медведева Ю.С. Быстрая нумерация слов, порождаемых грамматиками Дика // Математические заметки. - 2014. - Т.96. - № 1. - С.51-69. - ISSN 0025-567X. - EISSN 2305-2880.
Внешние системы: РИНЦ: 21826525;
Реферат: rus: Задача нумерации и денумерации слов, порождаемых грамматиками Дика, возникает при работе трансляторов для языков высокого уровня и в целом ряде других приложений. В данной работе предлагается алгоритм быстрой нумерации и денумерации слов языков Дика, сложность которого на один символ нумеруемого слова при использовании алгоритма умножения и деления Шёнхаге–Штрассена равна $O(\log^3 n \log \log n)$ битовых операций. Применение ранее известных методов имеет сложность $O(n)$ на один символ нумеруемого слова. Построение предложенного алгоритма основано на методе Б. Я. Рябко.
Библиография: 11 названий.
Издано: 2014
Физ. характеристика: с.51-69
Цитирование: 1. T. J. Lunch, “Sequence time coding for data compression”, Proc. IEEE, 54:10 (1966), 1490-1491 2. Ю. С. Медведева, Б. Я. Рябко, “Быстрый алгоритм нумерации слов с заданными ограничениями на длины серий единиц”, Пробл. передачи информ., 46:4 (2010), 130-139 3. T. M. Cover, “Enumerative Source Encoding”, IEEE Trans. Information Theory, IT-19:1 (1973), 73-77 4. Б. Я. Рябко, “Быстрая нумерация комбинаторных объектов”, Дискрет. матем., 10:2 (1998), 101-119 5. А. Е. Пентус, М. Р. Пентус, Теория формальных языков, Учебное пособие, Изд-во ЦПИ при мех.-мат. фак-те МГУ, М., 2004 6. Э. Рейнгольд, Ю. Нивергельт, Н. Део, Комбинаторные алгоритмы. Теория и практика, Мир, М., 1980 7. А. В. Ахо, М. С. Лам, Р. Сети, Д. Д. Ульман, Компиляторы. Принципы, технологии и инструментарий, Вильямс, М., 2008 8. Р. Е. Кричевский, Сжатие и поиск информации, Радио и связь, М., 1989 9. A. Schönhage, V. Strassen, “Schnelle Multiplikation grosser Zahlen”, Computing, 7:3-4 (1971), 281-292 10. M. Fürer, “Faster integer multiplication”, Proceedings of the 39th Annual ACM Symposium on Theory of Computing, ACM, New York, 2007, 57-66 11. А. Шень, Программирование: теоремы и задачи, МЦНМО, М., 2004