English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Constraint Database Models Characterizing Timed Bisimilarity

MPS-Authors
/persons/resource/persons45084

Mukhopadhyay,  Supratik
Programming Logics, MPI for Informatics, Max Planck Society;

/persons/resource/persons45201

Podelski,  Andreas
Programming Logics, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Mukhopadhyay, S., & Podelski, A. (2001). Constraint Database Models Characterizing Timed Bisimilarity. In I. Ramakrishnan (Ed.), Proceedings of the 3rd International Symposium on Practical Aspects of Declarative Languages (pp. 245-258). Berlin, Germany: Springer.


Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-31FD-3
Abstract
The problem of deciding timed bisimilarity has received increasing attention; it is important for verification of timed systems. Using a characterization of timed bisimilarity in terms of models of constraint databases, we present to our knowledge, the first \emph{local}, \emph{symbolic algorithm} for deciding timed bisimilarity; previous algorithms were based on a finite, but prohibitively large, abstraction (the region graph or the full backward stable graph). Our algorithm uses XSB-style tabling with constraints. Our methodology is more general than those followed in the previous approaches in the sense that our algorithm can be used to decide whether two timed systems are \emph{alternating timed bisimilar}.