### Abstract

In this paper, we compare Timed Automata (TA) with Time Petri Nets (TPN) with respect to weak timed bisimilarity. It is already known that the class of bounded TPNs is included in the class of TA. It is thus natural to try and identify the (strict) subclass T A^{wtb} of TA that is equivalent to TPN for the weak time bisimulation relation. We give a characterisation of this subclass and we show that the membership problem and the reachability problem for T A^{wtb} are PSPACE-complete. Furthermore we show that for a TA in T A^{wtb} with integer constants, an equivalent TPN can be built with integer bounds but with a size exponential w.r.t. the original model. Surprisingly, using rational bounds yields a TPN whose size is linear.

Original language | English |
---|---|

Title of host publication | FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science - 25th International Conference, Proceedings |

Place of Publication | New York |

Publisher | Springer, Springer Nature |

Pages | 273-284 |

Number of pages | 12 |

Volume | 3821 LNCS |

ISBN (Print) | 3540304959, 9783540304951 |

Publication status | Published - 2005 |

Externally published | Yes |

Event | 25th International Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2005 - Hyderabad, India Duration: 15 Dec 2005 → 18 Dec 2005 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 3821 LNCS |

ISSN (Print) | 03029743 |

ISSN (Electronic) | 16113349 |

### Other

Other | 25th International Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2005 |
---|---|

Country | India |

City | Hyderabad |

Period | 15/12/05 → 18/12/05 |

### Keywords

- Time Petri Nets
- Timed Automata
- Weak Timed Bisimilarity

## Fingerprint Dive into the research topics of 'When are timed automata weakly timed bisimilar to time petri nets?'. Together they form a unique fingerprint.

## Cite this

*FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science - 25th International Conference, Proceedings*(Vol. 3821 LNCS, pp. 273-284). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3821 LNCS). New York: Springer, Springer Nature.