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
13 January 2002
0 references
0.8435983657836914
0 references
0.6808738708496094
0 references
0.6675273776054382
0 references
0.6529985070228577
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