TUHH Open Research
Help
  • Log In
    New user? Click here to register.Have you forgotten your password?
  • English
  • Deutsch
  • Communities & Collections
  • Publications
  • Research Data
  • People
  • Institutions
  • Projects
  • Statistics
  1. Home
  2. TUHH
  3. Publication References
  4. On plain and hereditary history-preserving bisimulation
 
Options

On plain and hereditary history-preserving bisimulation

Publikationstyp
Conference Paper
Date Issued
1999
Sprache
English
Author(s)
Fröschle, Sibylle B.  orcid-logo
Hildebrandt, Thomas  
TORE-URI
http://hdl.handle.net/11420/11323
First published in
Lecture notes in computer science  
Number in series
1672 LCNS
Volume
1672
Start Page
354
End Page
365
Citation
Lecture Notes in Computer Science 1672: 354-365 (1999)
Contribution to Conference
24th International Symposium on Mathematical Foundations of Computer Science, MFCS 1999  
Publisher DOI
10.1007/3-540-48340-3_32
Scopus ID
2-s2.0-84949233239
Publisher
Springer
We investigate the difference between two well-known notions of independence bisimilarity, history-preserving bisimulation and hereditary history-preserving bisimulation. We characterise the difference between the two bisimulations in trace-theoretical terms, advocating the view that the first is (just) a bisimulation for causality, while the second is a bisimulation for concurrency. We explore the frontier zone between the two notions by defining a hierarchy of bounded backtracking bisimulations. Our goal is to provide a stepping stone for the solution to the intriguing open problem of whether hereditary history-preserving bisimulation is decidable or not. We prove that each of the bounded bisimulations is decidable. However, we also prove that the hierarchy is strict. This rules out the possibility that decidability of the general problem follows directly from the special case. Finally, we give a non trivial reduction solving the general problem for a restricted class of systems and give pointers towards a full answer.
DDC Class
004: Informatik
TUHH
Weiterführende Links
  • Contact
  • Send Feedback
  • Cookie settings
  • Privacy policy
  • Impress
DSpace Software

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science
Design by effective webwork GmbH

  • Deutsche NationalbibliothekDeutsche Nationalbibliothek
  • ORCiD Member OrganizationORCiD Member Organization
  • DataCiteDataCite
  • Re3DataRe3Data
  • OpenDOAROpenDOAR
  • OpenAireOpenAire
  • BASE Bielefeld Academic Search EngineBASE Bielefeld Academic Search Engine
Feedback