Multi-clock timed networks

被引:13
作者
Abdulla, PA [1 ]
Deneux, J [1 ]
Mahata, P [1 ]
机构
[1] Uppsala Univ, Uppsala, Sweden
来源
19TH ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, PROCEEDINGS | 2004年
关键词
D O I
10.1109/LICS.2004.1319629
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We consider verification of safety properties for parameterized systems of timed processes, so called timed networks. A timed network consists of a finite state process, called a controller and an arbitrary set of identical timed processes. In a previous work, we showed that checking safety properties is decidable in the case where each timed process is equipped with a single real-valued clock. It was left open whether the result could be extended to multi-clock timed networks. We show that the problem becomes undecidable when each timed process has two clocks. On the other hand, we show that the problem is decidable when clocks range over a discrete time domain. This decidability result holds when processes have any finite number of clocks.
引用
收藏
页码:345 / 354
页数:10
相关论文
共 19 条
[1]   Model checking of systems with many identical timed processes [J].
Abdulla, PA ;
Jonsson, B .
THEORETICAL COMPUTER SCIENCE, 2003, 290 (01) :241-264
[2]   Algorithmic analysis of programs with well quasi-ordered domains [J].
Abdulla, PA ;
Cerans, K ;
Jonsson, B ;
Tsay, YK .
INFORMATION AND COMPUTATION, 2000, 160 (1-2) :109-127
[3]   A THEORY OF TIMED AUTOMATA [J].
ALUR, R ;
DILL, DL .
THEORETICAL COMPUTER SCIENCE, 1994, 126 (02) :183-235
[4]  
ALUR R, 1993, LNCS, P592
[5]  
ANNICHINI A, 2000, LNCS, V1855
[6]   Timed regular expressions [J].
Asarin, E ;
Caspi, P ;
Maler, O .
JOURNAL OF THE ACM, 2002, 49 (02) :172-206
[7]  
BENGTSSON J, 1996, LECT NOTES COMPUTER, V1102, P244
[8]  
Delzanno G, 2000, Proc. 12th International Conference on Computer Aided Verification (CAV'00), P53
[10]  
EMERSON EA, 2003, P LICS 03