Temporal stratification tests for linear and branching-time deductive databases
| dc.contributor.author | Nomikos, C. | en |
| dc.contributor.author | Rondogiannis, P. | en |
| dc.contributor.author | Gergatsoulis, M. | en |
| dc.date.accessioned | 2015-11-24T17:01:03Z | |
| dc.date.available | 2015-11-24T17:01:03Z | |
| dc.identifier.issn | 0304-3975 | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/10863 | |
| dc.rights | Default Licence | - |
| dc.subject | temporal deductive databases | en |
| dc.subject | temporal logic programming | en |
| dc.subject | stratified negation | en |
| dc.subject | transformation technique | en |
| dc.subject | logic programs | en |
| dc.subject | negation | en |
| dc.title | Temporal stratification tests for linear and branching-time deductive databases | en |
| heal.abstract | We consider the problem of extending temporal deductive databases with stratified negation. We argue that the classical stratification test for deductive databases is too restrictive when one shifts attention to the temporal case. Moreover, as we demonstrate, the (more general) local stratification approach is impractical: detecting whether a temporal deductive database is locally stratified is shown to be co-NP hard (even if one restricts attention to programs that only use one predicate symbol and two constants). For these reasons we define temporal stratification, an intermediate notion between stratification and local stratification. We demonstrate that for the temporal deductive databases we consider, temporal stratification coincides with local stratification in certain important cases in which the latter is polynomial-time decidable. We then develop two algorithms for detecting temporal stratification. The first algorithm applies to linear-time temporal deductive databases and it is efficient and more general than existing approaches; however, the algorithm sacrifices completeness for efficiency since it does not cover the whole class of temporally stratified programs. The second algorithm applies to branching-time temporal deductive databases (which include as a special case the linear-time ones). This algorithm is more expensive from a computational point of view, but it covers the whole class of temporally stratified programs. We discuss the relative merits of the two algorithms and compare them with other existing approaches. (c) 2005 Elsevier B.V. All rights reserved. | en |
| heal.access | campus | - |
| heal.fullTextAvailability | TRUE | - |
| heal.identifier.primary | DOI 10.1016/j.tcs.2005.05.014 | - |
| heal.journalName | Theoretical Computer Science | en |
| heal.journalType | peer reviewed | - |
| heal.language | en | - |
| heal.publicationDate | 2005 | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.type | journalArticle | - |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.type.en | Journal article | en |
Αρχεία
Φάκελος/Πακέτο αδειών
1 - 1 of 1
Φόρτωση...
- Ονομα:
- license.txt
- Μέγεθος:
- 1.74 KB
- Μορφότυπο:
- Item-specific license agreed upon to submission
- Περιγραφή: