ГлавнаяАрхивО ПОСТРОЕНИИ МИНИМАЛЬНЫХ ДЕТЕРМИНИРОВАННЫХ КОНЕЧНЫХ АВТОМАТОВ, РАСПОЗНАЮЩИХ ПРЕФИКСНЫЙ КОД ЗАДАННОЙ МОЩНОСТИ

О ПОСТРОЕНИИ МИНИМАЛЬНЫХ ДЕТЕРМИНИРОВАННЫХ КОНЕЧНЫХ АВТОМАТОВ, РАСПОЗНАЮЩИХ ПРЕФИКСНЫЙ КОД ЗАДАННОЙ МОЩНОСТИ | Прикладная дискретная математика. 2010. № 2(8).

Рассматривается задача о построении минимального по числу состояний детерминированного конечного автомата, который принимает произвольный префиксный код заданной мощности над алфавитом {0,1}. Доказывается, что данная задача является эквивалентной задаче о поиске кратчайшей аддитивной цепочки, заканчивающейся числом п.
  • Title О ПОСТРОЕНИИ МИНИМАЛЬНЫХ ДЕТЕРМИНИРОВАННЫХ КОНЕЧНЫХ АВТОМАТОВ, РАСПОЗНАЮЩИХ ПРЕФИКСНЫЙ КОД ЗАДАННОЙ МОЩНОСТИ
  • Headline О ПОСТРОЕНИИ МИНИМАЛЬНЫХ ДЕТЕРМИНИРОВАННЫХ КОНЕЧНЫХ АВТОМАТОВ, РАСПОЗНАЮЩИХ ПРЕФИКСНЫЙ КОД ЗАДАННОЙ МОЩНОСТИ
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 2(8)
  • Date:
  • DOI
Ключевые слова
префиксный код, детерминированный конечный автомат, автомат Мура, аддитивная цепочка, prefix code, finite-state machine, Moore automaton, addition chain
Авторы
Ссылки
Han Y.-S., Salomaa K., Wood D. State complexity of prefix-free regular languages // Proc. of the 8th Int. Workshop on Descriptional Complexity of Formal Systems. 2006. P. 165-176.
Golin M. J., Na H. Optimal prefix-free codes that end in a specified pattern and similar problems: The uniform probability case (extended abstract) // Data Compression Conference. 2001. P. 143-152.
Unicode specification. <http://unicode.org/>.
Elias P. Universal codeword sets and representations of the integers // IEEE Trans. Inform. Theory. 1975. V.21. P. 194-203.
Хопкрофт Д. Э., Мотвани Р., Ульман Д. Д. Введение в теорию автоматов, языков и вычислений. М.: Вильямс, 2002. 528 с.
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, БИНОМ, 2004. 960 с.
Кнут Д. Э. Искусство программирования. Т. 2: Получисленные алгоритмы. М.: Вильямс, 2004. 832 с.
Bleichenbacher D. Efficiency and security of cryptosystems based on number theory. Zьrich, 1996.
Cruz-Cortes N., Rodriguez-Henriquez F., Juarez-Morales R., Coello C. A. Finding optimal addition chains using a genetic algorithm approach. LNCS. 2005. V. 3801. P. 208-215.
Nedjah N., de Macedo M. L. Finding minimal addition chains using ant colony // IDEAL / ed. by R. Y. Zheng, R. M. Everson, Y. Hujun. LNCS. 2004. V. 3177. P. 642-647.
Schonhage A. A lower bound for the length of addition chains // Theoretical Computer Science. 1975. V. 1. No. 1. P. 1-12.
Flammenkamp A. Shortest addition chains. <http://wwwhomes.uni-bielefeld.de/achim/>addition_chain.html.
Downey P., Leong B., Sethi R. Computing sequences with addition chains // SIAM J. Computing. 1981. V. 10. No.3. P. 638-646.
О ПОСТРОЕНИИ МИНИМАЛЬНЫХ ДЕТЕРМИНИРОВАННЫХ КОНЕЧНЫХ АВТОМАТОВ, РАСПОЗНАЮЩИХ ПРЕФИКСНЫЙ КОД ЗАДАННОЙ МОЩНОСТИ | Прикладная дискретная математика. 2010. № 2(8).
О ПОСТРОЕНИИ МИНИМАЛЬНЫХ ДЕТЕРМИНИРОВАННЫХ КОНЕЧНЫХ АВТОМАТОВ, РАСПОЗНАЮЩИХ ПРЕФИКСНЫЙ КОД ЗАДАННОЙ МОЩНОСТИ | Прикладная дискретная математика. 2010. № 2(8).
Полнотекстовая версия