Input-dependent-only object histories

摘要

In an earlier paper, one of the authors introduced a record-based model for describing historical data for objects (here called “object histories”). The primary 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. Now one of the components in a CSS is a finite set of constraints on object histories. In scanning some real-life object histories, it was noticed that some constraints involve only the “input” part of the histories. (The importance of this type of constraint is that in updating an object history, the satisfaction of the constraint by the new history can be checked in parallel with, rather than after, the computation about the new history.) In the present paper, this notion of input-dependent-only (IDO) constraint is abstracted and CSS in which each constraint is IDO are studied. Among the results obtained are the following: (i) necessary and sufficient conditions, as well as a practical sufficiency condition, for a set of object histories described by an arbitrary CSS to be described by another CSS having only IDO constraints, i.e., when a given CSS is IDO-representable or r-extended IDO-representable; and (ii) unsolvability results related to IDO constraints and the IDO representability for CSS.