Paper Info
Title
On decidability of prebisimulation for timed automata
Abstract
In this paper, we propose an at least as fast as relation between two timed automata states and investigate its decidability. The proposed relation is a prebisimulation and we show that given two processes with rational clock valuations it is decidable whether such a prebisimulation relation exists between them. Though bisimulation relations have been widely studied with respect to timed systems and timed automata, prebisimulations in timed systems form a much lesser studied area and according to our knowledge, this is the first of the kind where we study the decidability of a timed prebisimulation. This prebisimulation has been termed timed performance prebisimulation since it compares the efficiency of two states in terms of their performances in performing actions. if s and t are time abstracted bisimilar and every possible delay by s and its successors is no more than the delays performed by t and its successors where the delays are real numbers. The prebisimilarity defined here falls in between timed and time abstracted bisimilarity.
Year
DOI
Venue
2012
10.1007/978-3-642-31424-7_33
CAV
Keywords
Field
DocType
time abstracted bisimilarity,prebisimulation relation,possible delay,time abstracted bisimilar,real number,rational clock valuation,automata state,proposed relation,bisimulation relation,performance prebisimulation
Computer science,Automaton,Algorithm,Theoretical computer science,Decidability,Timed automaton,Bisimulation,Real number
Conference
Citations 
PageRank 
References 
4
0.47
24
Authors
3
Name
Order
Citations
PageRank
Shibashis Guha1158.55
Chinmay Narayan2533.53
S. Arun-Kumar341.49