Object histories which avoid certain subsequences (Q578943)

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.