350 rub
Journal Information-measuring and Control Systems №11 for 2009 г.
Article in number:
Checking up isomorphic inclusions of R-expressions in the construction of a set of sections for parallel logic control algorithms
Keywords: Parallel logic control algorithms R-expressions
Authors:
E. I. Vatutin, I. V. Zotov, V. S. Titov
Abstract:
In the paper, the problem of searching for isomorphic inclusions of R-expressions that arises while constructing a set of sections in the decomposition of parallel logic control algorithms is solved. A method for solving the problem is proposed which is capable of polynomial search for ismorphic substitutions on a tree-based representation of R-expressions. The method is shown to be sorrect based on a number of theorems proving that there exists the only isomorphic inclusion. Well-dnown analogous methods applicable to general case graphs are dnown to belong to the NP class. Our method may be extended to other similar problems, e. g., those solved by optimizing compilers.
Pages: 49-56
References
  1. Зотов И. В., Колосков В.А., Титов В. С. и др. Организация и синтез микропрограммных мультимикроконтроллеров. Курск: КурскГТУ, 1999.
  2. Зотов И. В., Колосков В. А., Титов В. С. Выбор оптимальных разбиений алгоритмов при проектировании микроконтроллерных сетей // Автоматика и вычислительная техника. 1997. № 5. С. 51-62.
  3. Ватутин Э. И., Зотов И. В. Поиск базового сечения в задаче разбиения параллельных алгоритмов. Курск. КГТУ. 2003. Рус. деп. в ВИНИТИ 24.11.03 № 2036-B2003.
  4. Ватутин Э. И., Зотов И. В., Титов В. С. Построение множества сечений в задаче оптимального разбиения параллельных управляющих алгоритмов // Изв. ТулГУ. Сер. Вычислительная техника. Информационные технологии. Системы управления. Тула: ТулГУ. 2003. Т. 1. Вып. 2. С. 70-77.
  5. Ватутин Э. И., Зотов И. В. Метод формирования субоптимальных разбиений параллельных управляющих алгоритмов // Параллельные вычисления и задачи управления (PACO-04). М.: ИПУ РАН. 2004. С. 884-917.
  6. Ватутин Э. И., Зотов И. В. Программная система для построения разбиений параллельных управляющих алгоритмов // Идентификация систем и задачи управления (SICPRO-06). М.: ИПУ РАН, 2006. С. 2239-2250.
  7. Свидетельство об официальной регистрации программы для ЭВМ № 2007613222. Визуальная среда синтеза разбиений параллельных алгоритмов логического управления // Ватутин Э. И., Зотов И. В. 2007.
  8. Ватутин Э. И., Волобуев С. В., Зотов И. В. Комплексная сравнительная оценка методов выбора разбиений при проектировании логических мультиконтроллеров // Идентификация систем и задачи управления (SICPRO-08). М.: ИПУ РАН. 2008. С. 1917-1940.
  9. Зыков А. А. Основы теории графов. М.: Наука. 1987.
  10. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений: Пер. с англ. 2-е изд. М.: Вильямс. 2002.
  11. Ватутин Э. И., Зотов И. В. Аппаратная модель для определения минимального числа блоков при декомпозиции параллельных алгоритмов логического управления // Изв. вузов. Сер. Приборостроение. 2008. Т. 51. № 2. С. 39-43.
  12. А. с. СССР № 596951, МКИ3G06F15/20. Устройство для определения изоморфизма графов / В. М. Курейчик, В. А. Калашников, А. Г. Королёв. 1978.
  13. А. с. СССР № 732879, МКИ3G06F15/20. Устройство для определения изоморфизма ориентированных графов / А. Г. Королёв, В. М. Курейчик, В. А. Калашников. 1980.