Процедура минимизации для некоторого подкласса многоленточных автоматов
Minimization procedure for some subclass of multitape automaton

УДК 519.1: 681.3

Статья посвящена решению задачи минимизации для подмножества многоленточных автоматов. Предлагается решение, которое описано в виде процедуры минимизации.

Article is devoted to the solution of a problem of minimization for a subset of multitape automaton. The decision which is described in the form of minimization procedure is offered.

Авторы:

Великая Яна Геннадьевна

НИУ «Белгородский государственный университет», г. Белгород
Кандидат технических наук, ст. преподаватель кафедры «Математическое и программное обеспечение информационных систем»

Сунцова Анастасия Игоревна

НИУ «Белгородский государственный университет», г. Белгород
Ассистент кафедры «Математическое и программное обеспечение информационных систем»

Чуев Евгений Викторович

НИУ «Белгородский государственный университет», г. Белгород
Студент кафедры «Математическое и программное обеспечение информационных систем»

Список цитируемой литературы:

  • Tamm H. On Minimality and Size Reduction of One-Tape and Multitape Finite Automata // University of Helsinki, Helsinki, 2004. Heory 34, 5 (1988), P. 1049-1053. 
  • Подловченко Р.И, Хачатрян В. Е. Минимальность и тупиковость многоленточных автоматов // Дискретная математика, 2008. – № 2. – С. 92-120. 
  • Watson B.-W., Daciuk. J. An efficient incremental DFA minimization algorithm. Natural Language Engineering, 9(1):49–64, march 2003. 
  • Jiang T.and Ravikumar B.. Minimal NFA problems are hard. SIAM J.Comput. 1993. – Vol. 22. – № 6. – P. 1117-1141. 
  • Kameda T., Weiner P. On the state minimization of nondeterministic automata. IEEE Trans. Comput. C-19, 7 (1970). – P. 617-627.
  • Hopcroft J. An n log n algorithm for minimizing states in a finite automaton. Technical Report CS-190, Stanford University, 1971. 
  • Хачатрян В.Е. Решение обобщенной проблемы минимизации для двухленточных автоматов с одной фиксированной лентой // ДАН, 2006. Том 411. – № 3. – С. 314-318. 
  • Подловченко Р.И. О проблеме эквивалентных преобразований программ // Программирование, 1986. – № 6. – С. 3-14 
  • Подловченко Р.И., Хачатрян В.Е.Полное решение проблемы минимизации для одного множества бинарных двухленточных автоматов //Дискретная математика, 2010. – Том 22. – Выпуск 3. – С. 146-159. 
  • Подловченко Р.И., Хачатрян В.Е., Чашин Ю.Г. Полная система эквивалентных преобразований для двухленточных автоматов с непересекающимися циклами // Программирование, 2000. – №5. – С.1-19. 

Последние новости

Случайный материал

  • В статье рассматриваются вопросы эффективной организации мониторинга процессов оказания электронных услуг. В качестве инструмента проведения мониторинга предлагается использовать автоматизированную систему, обеспечивающую адаптивную организацию процессов сбора, хранения и обработки данных. Сформулированы системные и технологические задачи организации мониторинга, раскрыты их сущность и принципы решения.
    Фролов Алексей Иванович, ФГБОУ ВПО «Госуниверситет – УНПК», г. Орел
  • В данной статье рассматриваются подходы к созданию подсистемы стабилизации температуры в барокамере экспериментальной системы контроля качества приборов. Данная подсистема позволяет управлять величиной тока, подаваемого на термоэлектрический модуль, для поддержания воздушной среды управляемого объекта – барокамеры в пределах заданной величины.
    Демина Юлия Александровна, ФГБОУ ВПО «Госуниверситет – УНПК», г. Орел
    Вереницын Андрей Игоревич, ФГБОУ ВПО «Госуниверситет – УНПК», г. Орел
    Демина Елена Григорьевна, ФГБОУ ВПО «Госуниверситет – УНПК», г. Орел
  • В данной статье рассматривается актуальность применения свободного программного обеспечения для оказания электронных услуг населению, а также выявляются проблемы при его внедрении и сопровождении.
    Стычук Алексей Александрович, ФГБОУ ВПО «Госуниверситет – УНПК», г. Орел
    Постников Максим Владимирович, ФГБОУ ВПО «Госуниверситет – УНПК», г. Орел