Object histories which avoid certain subsequences (Q578943)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Object histories which avoid certain subsequences |
scientific article |
Statements
Object histories which avoid certain subsequences (English)
0 references
1987
0 references
The paper follows a model of historical databases introduced by \textit{S. Ginsburg} and \textit{K. Tanaka} [ACM Trans. Database Syst. 11, 186-212 (1986; Zbl 0602.68098)], based on the notions of computation-tuple sequences and object histories. A computation-tuple sequence scheme specifies the set of all possible valid object histories for the same type of objects. The satisfaction of various kinds of constraints by an object history can be formulated in terms of sequences which avoid ''bad sequences'' as a subsequence. This leads to the notion of a bad- subsequence constraint. The so-called representability problem is studied, i.e. whether and when a particular set of object histories can be defined by some computation-tuple sequence scheme having all its constraints of a certain kind. Characterizations of representability by various types of bad-subsequence constraints (general bad-subsequence, bad-subsequence, functional and local) are given. Neither recognition algorithms nor their complexity are considered.
0 references
historical databases
0 references
computation-tuple sequences
0 references
object histories
0 references
bad- subsequence constraint
0 references
representability
0 references