UniSa - IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishWe consider the optimal-reachability problem for a timed automaton with respect to a linear cost function which results in a weighted timed automaton. Our solution to this optimization problem consists of reducing it to computing (parametric) shortest paths in a finite weighted directed graph. We call this graph a parametric sub-region graph. It refines the region graph, a standard tool for the analysis of timed automata, by adding the information which is relevant to solving the optimal-reachability problem. We present an algorithm to solve the optimal-reachability problem for weighted timed automata that takes time exponential in View the MathML source, where n is the number of clocks, |δ(A)| is the size of the clock constraints and |wmax| is the size of the largest weight. We show that this algorithm can be improved, if we restrict to weighted timed automata with a single clock. In case we consider a single starting state for the optimal-reachability problem, our approach yields an algorithm that takes exponential time only in the length of clock constraints.
| Titolo: | Optimal paths in weighted timed automata |
| Autori: | |
| Data di pubblicazione: | 2004 |
| Rivista: | |
| Abstract: | We consider the optimal-reachability problem for a timed automaton with respect to a linear cost function which results in a weighted timed automaton. Our solution to this optimization problem consists of reducing it to computing (parametric) shortest paths in a finite weighted directed graph. We call this graph a parametric sub-region graph. It refines the region graph, a standard tool for the analysis of timed automata, by adding the information which is relevant to solving the optimal-reachability problem. We present an algorithm to solve the optimal-reachability problem for weighted timed automata that takes time exponential in View the MathML source, where n is the number of clocks, |δ(A)| is the size of the clock constraints and |wmax| is the size of the largest weight. We show that this algorithm can be improved, if we restrict to weighted timed automata with a single clock. In case we consider a single starting state for the optimal-reachability problem, our approach yields an algorithm that takes exponential time only in the length of clock constraints. |
| Handle: | http://hdl.handle.net/11386/1068697 |
| Appare nelle tipologie: | 1.1.2 Articolo su rivista con ISSN |
File in questo prodotto:
Copyright © 2020