Fränzle, Martin and Shirmohammadi, Mahsa and Swaminathan, Mani and Worrell, James (2018) Costs and rewards in priced timed automata. In: 45th International Colloquium on Automata, Languages, and Programming: ICALP 2018, July 9-13, 2018, Prague, Czech Republic.

Preview

- Accepted Version Volltext (660Kb)

Abstract

We consider Pareto analysis of reachable states of multi-priced timed automata (MPTA): timed automata equipped with multiple observers that keep track of costs (to be minimised) and rewards (to be maximised) along a computation. Each observer has a constant non-negative derivative which may depend on the location of the MPTA. We study the Pareto Domination Problem, which asks whether it is possible to reach a target location via a run in which the accumulated costs and rewards Pareto dominate a given objective vector. We show that this problem is undecidable in general, but decidable for MPTA with at most three observers. For MPTA whose observers are all costs or all rewards, we show that the Pareto Domination Problem is PSPACE-complete. We also consider an epsilon-approximate Pareto Domination Problem that is decidable without restricting the number and types of observers. We develop connections between MPTA and Diophantine equations. Undecidability of the Pareto Domination Problem is shown by reduction from Hilbert's 10th Problem, while decidability for three observers is shown by a translation to a fragment of arithmetic involving quadratic forms

Item Type:	Conference or Workshop Item (Paper)
Additional Information:	A shorter version of this publication appears in the proceedings of ICALP 2018.
Uncontrolled Keywords:	Theory of Computation: Timed and Hybrid Models; Priced Timed Automata; Pareto Domination; Diophantine Equations;
Subjects:	Generalities, computers, information > Computer science, internet Science and mathematics > Mathematics
Divisions:	School of Computing Science, Business Administration, Economics and Law > Department of Computing Science
Date Deposited:	06 Sep 2018 09:02
Last Modified:	06 Sep 2018 09:02
URI:	https://oops.uni-oldenburg.de/id/eprint/3589
URN:	urn:nbn:de:gbv:715-oops-36703
DOI:
Nutzungslizenz:

Actions (login required)

View Item