hello,
in Exercise 9.2
there are no strong low bisimulations on programs for:
a) ii) ([skip], [l1 := 0])
iii) ([l1 := 0||l1 := 1], [l1 :=1||l1 := 0])
b) i) ([S], [S]) where S = (l2 := 0; if l2 = 0 then l1 := 0 else l1 := h1 fi)
But do I see right that there are actually strong low bisimulations on configurations in these cases, i.e. for:
-(([skip], sigma), ([l1 := 0], sigma')) for each low-equal sigma, sigma' with sigma(l1)=0(=sigma'(l1))
e.g. R:= symmetric closure of
{(([skip], sigma), ([l1 := 0], sigma')),
(([], sigma), ([], sigma'))}
-(([l1:=0||l1:=1], sigma), ([l1:=1||l1:=0], sigma')) for each low-equal sigma, sigma'
e.g. R := symmetric closure of
{(([l1:=0||l1:=1], sigma), ([l1:=1||l1:=0], sigma')),
(([l1:=1], sigma[l1/0]), ([l1:=1], sigma'[l1/0])),
(([l1:=0], sigma[l1/1]), ([l1:=0], sigma'[l1/1])),
(([], sigma[l1/1]), ([], sigma'[l1/1])),
(([], sigma[l1/0]), ([], sigma'[l1/0]))}
-((S, sigma), (S, sigma')) for each for each low-equal sigma, sigma'
(where again S = (l2 := 0; if l2 = 0 then l1 := 1 else l1 := h1 fi))
e.g. R:= symmetric closure of
{(([S], sigma), ([S], sigma')),
(([if l2=0 ...], sigma[l2/0]), ([if l2=0 ...], sigma'[l2/0])),
(([l1:=0], sigma[l2/0]), ([l1:=0], sigma'[l2/0])),
(([], sigma[l2/0][l1/0]), ([], sigma'[l2/0][l1/0]))}
the differences between strong low bisimulations on configurations and strong low bisimulations on programs,
I think are,
-that in strong low bisimulations on configurations the states are part of the places of the transitions system,
whereas in the strong low bisimulations on programs they are not (resulting in an different result for 9.2 b) i) ) and
-that in the definition of strong low bisimulations on programs the right hand program L1' needs to execute the same thread (i) as the left hand program L1 (whenever L1 R L1'),
whereas this is not required in the definition of strong low bisimulations on configurations
(leading to the different result for 9.2 a) iii) ).
So I conclude that:
- forall low-equal sigma, sigma', (L, sigma) "strongly low bisimilar on configurations" to (L', sigma'),
does not imply
- L "strongly low bisimilar on programs" to L',
is this correct?
best regards,
Alexander
Strong Low Bisimulation on Configurations and Strong Low Bisimulation on Programs
-
- BASIC-Programmierer
- Beiträge: 140
- Registriert: 2. Mai 2010 17:55
Strong Low Bisimulation on Configurations and Strong Low Bisimulation on Programs
Beitrag von AlexanderF » 22. Jan 2018 15:15
Re: Strong Low Bisimulation on Configurations and Strong Low Bisimulation on Programs
Beitrag von ximl » 28. Jan 2018 14:51
Hi Alexander,
I did not read in detail all your arguments about the example
programs, but it is correct that for each of the examples
a strong low bisimulation on configurations can be constructed
such that the pairing of the two programs with some pair/
all pairs of low equal states is in the bisimulation relation.
It is also correct that
- \forall \sigma, \sigma'. \sigma "low equals" \sigma' =>
<L, \sigma> "strongly low bisimilar on config. to" <L', \sigma'>
does not imply
- L "strongly low bisimilar on programs to" L'
With our definitions, "strong low bisimulation on configurations"
takes a global perspective, and comes with the assumption that
the states cannot be modified by the environment of a multi-threaded
program. On the other hand, "strong low bisimulation on programs"
takes a local perspective, and comes with the assumption that
the states might be modified by the environment of a thread.
Note that, in general, it is still possible to obtain strong low
bisimulation on programs from a suitable definition of strong
low bisimulation on configurations, using a product construction.
Best regards,
Ximeng
I did not read in detail all your arguments about the example
programs, but it is correct that for each of the examples
a strong low bisimulation on configurations can be constructed
such that the pairing of the two programs with some pair/
all pairs of low equal states is in the bisimulation relation.
It is also correct that
- \forall \sigma, \sigma'. \sigma "low equals" \sigma' =>
<L, \sigma> "strongly low bisimilar on config. to" <L', \sigma'>
does not imply
- L "strongly low bisimilar on programs to" L'
With our definitions, "strong low bisimulation on configurations"
takes a global perspective, and comes with the assumption that
the states cannot be modified by the environment of a multi-threaded
program. On the other hand, "strong low bisimulation on programs"
takes a local perspective, and comes with the assumption that
the states might be modified by the environment of a thread.
Note that, in general, it is still possible to obtain strong low
bisimulation on programs from a suitable definition of strong
low bisimulation on configurations, using a product construction.
Best regards,
Ximeng
Gehe zu Forum
- Allgemeines
- ↳ Neuigkeiten
- ↳ Ankündigungen
- ↳ Studienberatung
- ↳ Aktive Fachschaft
- ↳ Allgemein
- ↳ Forumsanregungen
- ↳ Inforz
- ↳ Das Wesentliche
- ↳ Vor dem Studium
- ↳ Studieninteressierte
- ↳ Vorkurs
- ↳ Archiv
- ↳ Ophase
- ↳ Archiv
- ↳ Studium
- ↳ Allgemein
- ↳ Ausland
- ↳ Bachelorpraktikum
- ↳ Archiv
- ↳ RBG/Rechner
- ↳ Studienorganisation
- ↳ Teilzeitstudium
- ↳ Angebote
- ↳ Abschlussarbeiten
- ↳ Jobs
- ↳ Umfragen
- ↳ Veranstaltungen
- ↳ Sonstiges
- ↳ GnoM
- ↳ RPGnoM
- ↳ Offtopic
- ↳ TU Darmstadt Programming-Contest
- ↳ CrypTool
- ↳ Suche / Biete
- ↳ Archiv
- Pflichtveranstaltungen
- ↳ Grundstudium
- ↳ Aussagen- und Prädikatenlogik
- ↳ Archiv
- ↳ Algorithmen und Datenstrukturen
- ↳ AuD: Vorlesung
- ↳ Archiv
- ↳ AuD: Theoretische Aufgaben
- ↳ Archiv
- ↳ AuD: Arbeit mit Nabla
- ↳ Archiv
- ↳ AuD: Programmieraufgaben
- ↳ Archiv
- ↳ AuD: Rund um die Klausur
- ↳ Archiv
- ↳ Automaten, formale Sprachen und Entscheidbarkeit
- ↳ Archiv
- ↳ Betriebssysteme
- ↳ Archiv
- ↳ Digitaltechnik
- ↳ Archiv
- ↳ Einführung in den Compilerbau
- ↳ Archiv
- ↳ Funktionale und Objektorientierte Programmierkonzepte
- ↳ Archiv
- ↳ GdI 1: Vorlesung
- ↳ Archiv
- ↳ GdI 1: Übung
- ↳ Archiv
- ↳ GdI 1: Praktikum
- ↳ Archiv
- ↳ Mathematik für Informatik 1
- ↳ Archiv
- ↳ Mathematik für Informatik 2
- ↳ Archiv
- ↳ Mathematik für Informatik 3
- ↳ Archiv
- ↳ Rechnerorganisation
- ↳ Archiv
- ↳ Systemnahe und parallele Programmierung
- ↳ Archiv
- ↳ Weiterführende Pflichtveranstaltungen
- ↳ Architekturen und Entwurf von Rechnersystemen
- ↳ Archiv
- ↳ Computational Engineering und Robotik
- ↳ Archiv
- ↳ Computer-Netzwerke und verteilte Systeme
- ↳ Archiv
- ↳ Computersystemsicherheit
- ↳ Archiv
- ↳ Informationsmanagement
- ↳ Archiv
- ↳ Modellierung, Spezifikation und Semantik
- ↳ Archiv
- ↳ Software Engineering
- ↳ Archiv
- ↳ Visual Computing
- ↳ Archiv
- ↳ Nicht mehr angeboten
- ↳ FGdI 3
- ↳ Archiv
- ↳ GdI 3
- ↳ GdI 3: Vorlesung
- ↳ Archiv
- ↳ GdI 3: Übung
- ↳ Archiv
- ↳ GdI 3: Praktikum
- ↳ Archiv
- ↳ TGdI
- ↳ Archiv
- ↳ TGdI 1
- ↳ Archiv
- ↳ TGdI 2
- ↳ Archiv
- Wahlbereich
- ↳ IT-Sicherheit
- ↳ Einführung in die Kryptographie
- ↳ Archiv
- ↳ Elektronische Wahlen
- ↳ Embedded System Security
- ↳ Formal Methods for Information Security
- ↳ Archiv
- ↳ Forschungskurs "Angewandte Kryptographie"
- ↳ IT-Sicherheit
- ↳ Archiv
- ↳ IT-Sicherheits-Management
- ↳ Kryptographische Protokolle
- ↳ Multimedia Security
- ↳ Netzsicherheit
- ↳ Operating Systems
- ↳ Archiv
- ↳ Operating Systems II: Dependability and Trust
- ↳ Archiv
- ↳ Post-Quantum Cryptography
- ↳ Praktikum: CAPTCHAs
- ↳ Praktikum: Kryptographie
- ↳ Praktikum: Sichere Informationssysteme
- ↳ Praktikum: Smartphone-Sicherheit für Android Applikationen
- ↳ Praktikum in der Lehre: Informatik Ferienworkshop
- ↳ Privacy Enhancing Technologies
- ↳ Public Key Infrastrukturen
- ↳ Archiv
- ↳ Public Key Kryptoanalyse
- ↳ Archiv
- ↳ Quantenalgorithmen
- ↳ Secure, Trusted and Trustworthy Computing, Teil 1
- ↳ Seminar: PhD Seminar ITS
- ↳ Seminar: Post Quantum Kryptographie
- ↳ Seminar: Sicherheit in Car2Car-Kommunikation
- ↳ Seminar: Usable Security
- ↳ Verfahren zur automatischen Verifikation
- ↳ Netze und Verteilte Systeme
- ↳ Kommunikationsnetze 1
- ↳ Kommunikationsnetze 2
- ↳ Kommunikationsnetze 3: Mobilität in Netzen
- ↳ Archiv
- ↳ Peer-to-Peer und Grid Computing
- ↳ Archiv
- ↳ Peer-to-Peer II - Methods
- ↳ Archiv
- ↳ Praktikum: Internet
- ↳ Praktikum: Kommunikation in Peer-to-Peer-Netzen
- ↳ Praktikum: Peer-to-Peer-Middleware
- ↳ TK1: Rechnernetze, Verteilte Systeme und Algorithmen
- ↳ Archiv
- ↳ TK2: Web Engineering, Web Cooperation und E-Learning
- ↳ TK3: Ubiquitous / Mobile Computing
- ↳ Ubiquitous Computing in Geschäftsprozessen
- ↳ Robotik, Computational und Computer Engineering
- ↳ Algorithmen im Chip-Entwurf
- ↳ Archiv
- ↳ Compiler 1
- ↳ Archiv
- ↳ Compiler 2
- ↳ Archiv
- ↳ Echtzeitsysteme
- ↳ Eingebettete Systeme 1
- ↳ Eingebettete Systeme 2
- ↳ Geometrische Methoden des CAD/CAE
- ↳ Grundlagen der Robotik
- ↳ Hardwaremodellierungssprachen
- ↳ Lernende Roboter
- ↳ Mainframe Technologie
- ↳ Optimierende Compiler
- ↳ Archiv
- ↳ Optimierung statischer und dynamischer Systeme
- ↳ Archiv
- ↳ Praktikum: Adaptive Computersysteme
- ↳ Praktikum: Embedded Systems Hands-On 1
- ↳ Prozessorarchitekturen für rechenstarke eingebettete Systeme
- ↳ Archiv
- ↳ Rekonfigurierbare Prozessoren
- ↳ Seminar: Dynamisch und partiell rekonfigurierbare Architekturen
- ↳ Software-Systeme und formale Grundlagen
- ↳ Algorithmische Modellierung
- ↳ Applied Static Analysis
- ↳ Automated Code Analysis for Large Software Systems
- ↳ Automated Software Engineering
- ↳ Automated Theorem Proving
- ↳ Berechenbarkeitstheorie
- ↳ Archiv
- ↳ Concepts and Technologies for Distributed Systems and Big Data Processing
- ↳ Archiv
- ↳ Design and Implementation of Modern Programming Languages
- ↳ Designing code analyses for large software systems (DECA)
- ↳ Effiziente Graphenalgorithmen
- ↳ Enterprise Application Design
- ↳ Archiv
- ↳ Grundlagen des KI Planens
- ↳ Implementing code analyses for large software systems (ICA)
- ↳ Konzepte der Programmiersprachen
- ↳ Archiv
- ↳ Modellierungspraktikum
- ↳ Optimierungsalgorithmen
- ↳ Praktikum: Algorithmen
- ↳ Praktikum: Proof-Carrying-Code
- ↳ Archiv
- ↳ Programmanalyse und Transformation
- ↳ Secure Coding Lab
- ↳ Secure Software Development (SecDev)
- ↳ Seminar: Current Topics in Information Flow Security
- ↳ Seminar: Current Topics in Usage Control
- ↳ Seminar: Formale Spezifikation
- ↳ Seminar: Proof-Carrying-Code
- ↳ Archiv
- ↳ Seminar: Reading Group Runtime Monitoring
- ↳ Seminar: Reliable Security for Concurrent Programs
- ↳ Seminar: Softwaresystemtechnologien
- ↳ Software Engineering - Design and Construction
- ↳ Archiv
- ↳ Software Engineering - Projekt
- ↳ Archiv
- ↳ Software Engineering - Projektmanagement
- ↳ Software Engineering - Requirements
- ↳ Software Engineering - Wartung und Qualitätssicherung
- ↳ Archiv
- ↳ Software Engineering in industrial practice
- ↳ Archiv
- ↳ Static and Dynamic Program Analysis
- ↳ Archiv
- ↳ Technikgestaltung
- ↳ Type Systems of Programming Languages
- ↳ Web Services Technologien: Einführung, Komposition und Erweiterungen
- ↳ Visual & Interactive Computing
- ↳ Advanced Programming Techniques in Computer Vision
- ↳ Bildverarbeitung
- ↳ Capturing Reality
- ↳ Computer Vision
- ↳ Computer Vision 2
- ↳ Context-Awareness
- ↳ Einführung in die Computermusik
- ↳ Game Technology
- ↳ Archiv
- ↳ Geometric Algebra Computing
- ↳ Archiv
- ↳ Graphische Datenverarbeitung 1
- ↳ Archiv
- ↳ Graphische Datenverarbeitung 2
- ↳ Archiv
- ↳ Graphische Informationssysteme
- ↳ Informationsvisualisierung und Visual Analytics
- ↳ IT-Management und IT-Einsatz
- ↳ Probabilistische Graphische Modelle
- ↳ Programming Massively Parallel Processors
- ↳ Archiv
- ↳ Seminar: Probleme in Computergraphik und Computer Vision
- ↳ Statistisches Maschinelles Lernen
- ↳ Serious Games
- ↳ Archiv
- ↳ Virtual and Augmented Reality
- ↳ Archiv
- ↳ Web, Wissens- und Informationsverarbeitung
- ↳ Algorithms of Language Technology
- ↳ Business Intelligence and Data Warehousing
- ↳ Datenbanken 2
- ↳ Data Mining und Maschinelles Lernen
- ↳ Archiv
- ↳ Digitale Spiele / Digital Games
- ↳ Einführung in die Künstliche Intelligenz
- ↳ Innovative Operating System Elements
- ↳ Middleware
- ↳ Natural Language Processing and the Web
- ↳ Praktikum: Data-Mining
- ↳ Praktikum: Künstliche Intelligenz
- ↳ Praktikum: Question Answering Technologies Behind IBM Watson
- ↳ Semantic Web
- ↳ Seminar: Deep Learning for NLP and Speech
- ↳ Seminar: Knowledge Management in Web 2.0
- ↳ Web Mining
- ↳ Fachübergreifender Anteil
- ↳ Einführung in wissenschaftliches Arbeiten
- ↳ Archiv
- ↳ Nicht mehr angeboten
- ↳ Digital Storytelling
- ↳ Graphische Datenverarbeitung 3
- ↳ Archiv
- ↳ Grundlagen der Rechnertechnologie
- ↳ Grundlagen des CAE/CAD 2
- ↳ Mobile sichere Systeme
- ↳ Netzwerksicherheit
- ↳ Praktikum: Spielerische Edutainment-Anwendungen / Game Technology
- ↳ Archiv
- ↳ Rechnerarchitektur
- ↳ Rechnerentwurf und Mikroprogrammierung
- ↳ Archiv
- ↳ Robotik 0: Mobile und sensorgeführte Robotiksysteme
- ↳ Robotik 1: Grundlagen
- ↳ Archiv
- ↳ Robotik 2: Mobilität und Autonomie
- ↳ Archiv
- ↳ Seminar: Rechnerarchitektur
- ↳ Systementwurf mit Mikroprozessoren
- ↳ Archiv
- ↳ Seminar: Digital Storytelling
- ↳ Archiv
- Masterstudium
- ↳ Neben- und Anwendungsfächer
- ↳ Archiv
- ↳ Spezialisierungsmaster
- ↳ Abschlussarbeiten
- ↳ Studienorganisation
- Serviceveranstaltungen
- ↳ AI 1
- ↳ Archiv
- ↳ AI 2
- ↳ Archiv
- ↳ AI 3
- ↳ Archiv