##
**Object-oriented data as prefix rewriting systems.**
*(English)*
Zbl 1463.68032

Summary: 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\)?

### MSC:

68Q42 | Grammars and rewriting systems |

68N19 | Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.) |

68P05 | Data structures |

68T30 | Knowledge representation |

### Keywords:

prefix rewriting; term rewriting; object-oriented data system; information system; consistency verification; ontology of data model
PDFBibTeX
XMLCite

\textit{A. E. Gutman}, Vladikavkaz. Mat. Zh. 17, No. 3, 23--35 (2015; Zbl 1463.68032)

Full Text:
MNR

### References:

[1] | Salomaa A., Formal Languages, Academic Press, N.Y., 1973, 336 pp. · Zbl 0262.68025 |

[2] | Barwise J. (ed.), Handbook of Mathematical Logic, North-Holland, Amsterdam, 1977, 1165 pp. |

[3] | Vizing V. G., “Distributive Coloring of Graph Vertices”, Diskretn. Anal. Issled. Oper., 2:4 (1995), 3-12 · Zbl 0860.05034 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.