Temporal networks are data structures for representing and reasoning about temporalconstraints on activities. Many kinds of temporal networks have been defined in theliterature, differing in their expressiveness. The simplest kinds of networks have polynomialalgorithms for determining their temporal consistency or different levels of controllability,but corresponding algorithms for more expressive networks (e.g., those that include observationnodes or disjunctive constraints) have so far been unavailable. This paper introduces anew approach to determine the dynamic controllability of a very expressive class of temporalnetworks that accommodates observation nodes and disjunctive constraints. The approach isbased on encoding the dynamic controllability problem into a reachability game for TimedGame Automata (TGAs). This is the first sound and complete approach for determining thedynamic controllability of such networks. The encoding also highlights the theoretical relationshipsbetween various kinds of temporal networks and TGAs. The new algorithms haveimmediate applications in the design and analysis of workflow models being developed toautomate business processes, including workflows in the healthcare domain.

Dynamic controllability via Timed Game Automata

POSENATO, Roberto;
2016

Abstract

Temporal networks are data structures for representing and reasoning about temporalconstraints on activities. Many kinds of temporal networks have been defined in theliterature, differing in their expressiveness. The simplest kinds of networks have polynomialalgorithms for determining their temporal consistency or different levels of controllability,but corresponding algorithms for more expressive networks (e.g., those that include observationnodes or disjunctive constraints) have so far been unavailable. This paper introduces anew approach to determine the dynamic controllability of a very expressive class of temporalnetworks that accommodates observation nodes and disjunctive constraints. The approach isbased on encoding the dynamic controllability problem into a reachability game for TimedGame Automata (TGAs). This is the first sound and complete approach for determining thedynamic controllability of such networks. The encoding also highlights the theoretical relationshipsbetween various kinds of temporal networks and TGAs. The new algorithms haveimmediate applications in the design and analysis of workflow models being developed toautomate business processes, including workflows in the healthcare domain.
Dynamic controllability, Temporal networks, Timed Game Automata
File in questo prodotto:
File Dimensione Formato  
posenatoACTAs00236-016-0257-2.pdf

solo utenti autorizzati

Descrizione: post-print
Tipologia: Documento in Post-print
Licenza: Accesso ristretto
Dimensione 478.82 kB
Formato Adobe PDF
478.82 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11562/935358
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 25
  • ???jsp.display-item.citation.isi??? 12
social impact