Object-oriented dataas prefix rewriting systems
A. E. Gutmanab
a Sobolev Institute of Mathematics, Laboratory of Functional Analysis, Acad. Koptyug av. 4, 630090, Novosibirsk, Russia
b Novosibirsk State University, Pirogova 2, 630090, Novosibirsk, Russia
A deterministic longest-prefix rewriting system is a rewriting system such that there are no rewriting rules $X\to Y$, $X\to Z$ with $Y\ne Z$, and only longest prefixes of words are subject to rewriting. Given such a system, analogs are defined and examined of some concepts related to object-oriented data systems: inheritance of classes and objects, instances of classes, class and instance attributes, conceptual dependence and consistency, conceptual scheme, types and subtypes, etc. A special attention is paid to the effective verification of various properties of the rewriting systems under consideration. In particular, algorithms are presented for answering the following questions: Are all words finitely rewritable? Do there exist recurrent words? Is the system conceptually consistent? Given two words $X$ and $Y$, does $X$ conceptually depend on $Y$? Does the type of $X$ coincide with that of $Y$? Is the type of $X$ a subtype of that of $Y$?
prefix rewriting, term rewriting, object-oriented data system, information system, consistency verification, ontology of a data model.
PDF file (267 kB)
MSC: 68Q42, 68P05, 68N19, 68T30
A. E. Gutman, “Object-oriented dataas prefix rewriting systems”, Vladikavkaz. Mat. Zh., 17:3 (2015), 23–35
Citation in format AMSBIB
\paper Object-oriented dataas prefix rewriting systems
\jour Vladikavkaz. Mat. Zh.
Citing articles on Google Scholar:
Related articles on Google Scholar:
|Number of views:|