Computational and structural aspects of openly specified type hierarchies (Q2762869)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1689578
Language Label Description Also known as
default for all languages
No label defined
    English
    Computational and structural aspects of openly specified type hierarchies
    scientific article; zbMATH DE number 1689578

      Statements

      0 references
      13 January 2002
      0 references
      Computational and structural aspects of openly specified type hierarchies (English)
      0 references
      One may identify two main approaches to the description of type hierarchies. In \textit{total specification}, a unique hierarchy is described. In \textit{open specification}, a set of constraints identifies properties of the hierarchy, without providing a complete description. Open specification provides increased expressive power, but at the expense of considerable computational complexity, with essential tasks being NP-complete or NP-hard. In this work, a formal study of the structural and computational aspects of open specification is conducted, so that a better understanding of how techniques may be developed to address these complexities. In addition, a technique is presented, based upon Horn clauses, which allows one to obtain answers to certain types of queries on open specifications very efficiently. For the entire collection see [Zbl 0967.00057].
      0 references

      Identifiers