Объектно-ориентированные данные и префиксная перезапись. Часть I: Обзор и основные результаты

Объектно-ориентированные данные и префиксная перезапись. Часть I: Обзор и основные результаты

Гутман А. Е.
Сибирский математический журнал, 67, 3, 392-413 (2026)
Скачать статью

УДК 519.682.1+519.683+519.7+519.1 
DOI: 10.33048/smzh.2026.67.302

Аннотация:

Детерминированная префиксная перезаписывающая система представляет собой систему перезаписи строк, не содержащую пар правил вида $X \to Y $, $X \to Z$, где $Y \ne Z$, в которой перезаписи подлежат только самые длинные префиксы. Для таких систем определяются и исследуются аналоги понятий, характерных для объектно-ориентированных систем данных: наследование классов и объектов, экземпляры классов, атрибуты классов и экземпляров, концептуальная зависимость и непротиворечивость, концептуальная схема, типы, подтипы и др. Особое внимание уделяется алгоритмической проверке различных свойств рассматриваемых перезаписывающих систем.

Литература:
  1. Büchi J. R. Regular canonical systems // Arch. Math. Logik Grundlag. 1964. V. 6. P. 91–111.
     
  2. Caucal D. On the regular structure of prefix rewriting // Theoret. Comput. Sci. 1992. V. 106, N 1. P. 61–86.
     
  3. Book R. V., Otto F. String-rewriting systems. New York: Springer, 1993.
     
  4. Frazier M., Page C. D. Prefix grammars: An alternative characterization of the regular languages // Inform. Process. Lett. 1994. V. 51, N 2. P. 67–71.
     
  5. Cardelli L., Wegner P. On understanding types, data abstraction, and polymorphism // ACM Comput. Surv. 1985. V. 17, N 4. P. 471–523.
     
  6. Аткинсон М., Бансилон Ф., ДеВитт Д., Диттрих К., Майер Д., Здоник С. Манифест систем объектно-ориентированных баз данных // Системы управления базами данных. 1995. № 4.
     
  7. Dittrich K. R. Object-oriented data model concepts // Advances in Object-Oriented Database Systems. Berlin: Springer, 1994. P. 29–45.
     
  8. Харари Ф. Теория графов. Москва: Мир, 1973.
     
  9. Gutman A. E. Object-oriented data as prefix rewriting systems // Vladikavkaz. Mat. Zh. 2015. V. 17, N 3. P. 23–35.
     
  10. Саломаа А. Жемчужины теории формальных языков. Москва: Мир, 1986.
     
  11. Барвайс Дж. Справочная книга по математической логике. Часть III: Теория рекурсии. Москва: Наука, 1982.
     
  12. Визинг В. Г. Дистрибутивная раскраска вершин графа // Дискрет. анализ и исслед. операций. 1995. Т. 2, № 4. С. 3–12.

Работа выполнена в рамках государственного задания ИМ СО РАН (проект № FWNF– 2026–0022).

Гутман Александр Ефимович (ORCID 0000-0003-2030-7459)
  1. Институт математики им. С. Л. Соболева СО РАН, 
    пр. Академика Коптюга, 4, Новосибирск 630090

E-mail: gutman@math.nsc.ru 

Статья поступила 15 января 2026 г. 
После доработки — 15 января 2026 г.
Принята к публикации 7 апреля 2026 г.