Gutman A.E.
Object-oriented data as prefix rewriting systems //
Владикавк. мат. журн. 2015. Т. 17, вып. 3. С. 23–35.
Рассматриваются перезаписывающие системы, не содержащие пар правил вида X → Y, X → Z, где Y ≠ Z, в которых перезаписи подлежат только самые длинные префиксы. В рамках таких систем определяются и исследуются аналоги концепций, характерных для систем объектно-ориентированных данных: наследование классов и объектов, экземпляры классов, атрибуты экземпляров и классов, концептуальная зависимость и непротиворечивость, концептуальные схемы, типы, подтипы и др. Особое внимание уделяется эффективной проверке разнообразных свойств рассматриваемых перезаписывающих систем. В частности, приводятся алгоритмы для ответа на следующие вопросы: Все ли слова конечно переписываемы? Существуют ли рекуррентные слова? Является ли система концептуально непротиворечивой? Концептуально зависит ли данное слово X от слова Y? Совпадают ли типы X и Y? Является ли тип X подтипом типа Y?
Ключевые слова:префиксная перезаписывающая система, полутуэвская система, система объектно-ориентированных данных, информационная система, проверка непротиворечивости, онтология модели данных.