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
    0 references
    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

    Identifiers