Loading...
Please wait, while we are loading the content...
Similar Documents
On the Language Inclusion Problem for Timed Automata: Closing a Decidability Gap (2003)
| Content Provider | CiteSeerX |
|---|---|
| Author | Ouaknine, Joel Worrell, James |
| Description | In Proceedings of LICS 04, IEEE Computer We consider the language inclusion problem for timed automata: given two timed automata A and B, are all the timed traces accepted by B also accepted by A? While this problem is known to be undecidable, we show here that it becomes decidable if A is restricted to having at most one clock. This is somewhat surprising, since it is well-known that there exist timed automata with a single clock that cannot be complemented. The crux of our proof consists in reducing the language inclusion problem to a reachability question on an in nite graph; we then construct a suitable well-quasi-order on the nodes of this graph, which ensures the termination of our search algorithm. |
| File Format | |
| Language | English |
| Publisher | Society Press |
| Publisher Date | 2003-01-01 |
| Access Restriction | Open |
| Subject Keyword | Decidability Gap Timed Automaton Nite Graph Language Inclusion Problem Suitable Well-quasi-order Single Clock Reachability Question Search Algorithm Timed Trace |
| Content Type | Text |
| Resource Type | Article |
