Object histories which avoid certain subsequences

In an earlier paper, one of the authors introduced a record-based model for describing historical data for objects (here called “object histories”). The major construct in the model is a computation-tuple sequence scheme (abbreviated CSS) which specifies the set of all “valid” object histories for the same type of object. In follow-up articles, the effects of interval queries and projections on object histories were examined. Now one of the components in a CSS is a finite set of constraints on object histories. In the present investigation the notion of bad-subsequence constraint is defined and CSS in which each constraint is of this kind are studied. (A bad-subsequence constraint σ is specified by a given set b of object histories. An object history u satisfies σ if u has no subsequence which is a sequence in b.) Among the results are the following: (i) Necessary and sufficient conditions for a set of object histories described by a given CSS to be described by another CSS having only bad-subsequence constraints, i. e. , when a given CSS is bad-subsequence representable; (ii) a characterization for when a bad-subsequence-representable CSS is also locally representable (in the sense of one of the earlier papers); and (iii) connections of bad-subsequence representability with functional-dependency representability.

Authors

• Seymour Ginsburg
• Marc Gyssens

Keywords

No keywords are indexed for this paper.