Temporal Reasoning in Nested Temporal Networks with Alternatives

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F08%3A00100903" target="_blank" >RIV/00216208:11320/08:00100903 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Temporal Reasoning in Nested Temporal Networks with Alternatives
Original language description
Temporal networks play a crucial role in modeling temporal relations in planning and scheduling applications. Temporal Networks with Alternatives (TNAs) were proposed to model alternative and parallel processes in production scheduling, however the problem of deciding which nodes can be consistently included in such networks is NP-complete. A tractable subclass, called Nested TNAs, can still cover a wide range of real-life processes, while the problem of deciding node validity is solvable in polynomialtime. In this paper, we show that adding simple temporal constraints (instead of precedence relations) to Nested TNAs makes the problem NP-hard again. We also present several complete and incomplete techniques for temporal reasoning in Nested TNAs.
Czech name
Uvažování o čase v zahnízděných temporálních sítích s alternativami
Czech description
Článek pojednává o temporálních podmínkách v temporálních sítích s alternativami. Ukazuje, že temporální uvažovaní je NP-úplné, a je zde navrženo několik algoritmů pro temporální propagace (úplné i neúplné).

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2008
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)