Techniques for Decidability and Undecidability of Bisimilarity View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1999

AUTHORS

Petr Jančar , Faron Moller

ABSTRACT

In this tutorial we describe general approaches to deciding bisimilarity between vertices of (infinite) directed edge-labelled graphs. The approaches are based on a systematic search following the definition of bisimilarity. We outline (in decreasing levels of detail) how the search is modified to solve the problem for finite graphs, BPP graphs, BPA graphs, normed PA graphs, and normed PDA graphs. We complete this by showing the technique used in the case of graphs generated by onecounter machines. Finally, we demonstrate a general reduction strategy for proving undecidability, which we apply in the case of graphs generated by state-extended BPP (a restricted form of labelled Petri nets). More... »

PAGES

30-45

Book

TITLE

CONCUR’99 Concurrency Theory

ISBN

978-3-540-66425-3
978-3-540-48320-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-48320-9_5

DOI

http://dx.doi.org/10.1007/3-540-48320-9_5

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1027984004


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0806", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information Systems", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Technical University of Ostrava, Czech Republic", 
          "id": "http://www.grid.ac/institutes/grid.440850.d", 
          "name": [
            "Technical University of Ostrava, Czech Republic"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Jan\u010dar", 
        "givenName": "Petr", 
        "id": "sg:person.07724710171.43", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07724710171.43"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Uppsala University, Sweden", 
          "id": "http://www.grid.ac/institutes/grid.8993.b", 
          "name": [
            "Uppsala University, Sweden"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Moller", 
        "givenName": "Faron", 
        "id": "sg:person.010425236217.29", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010425236217.29"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1999", 
    "datePublishedReg": "1999-01-01", 
    "description": "In this tutorial we describe general approaches to deciding bisimilarity between vertices of (infinite) directed edge-labelled graphs. The approaches are based on a systematic search following the definition of bisimilarity. We outline (in decreasing levels of detail) how the search is modified to solve the problem for finite graphs, BPP graphs, BPA graphs, normed PA graphs, and normed PDA graphs. We complete this by showing the technique used in the case of graphs generated by onecounter machines. Finally, we demonstrate a general reduction strategy for proving undecidability, which we apply in the case of graphs generated by state-extended BPP (a restricted form of labelled Petri nets).", 
    "editor": [
      {
        "familyName": "Baeten", 
        "givenName": "Jos C. M.", 
        "type": "Person"
      }, 
      {
        "familyName": "Mauw", 
        "givenName": "Sjouke", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-48320-9_5", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-66425-3", 
        "978-3-540-48320-5"
      ], 
      "name": "CONCUR\u201999 Concurrency Theory", 
      "type": "Book"
    }, 
    "keywords": [
      "systematic search", 
      "cases", 
      "reduction strategies", 
      "search", 
      "strategies", 
      "technique", 
      "approach", 
      "definition", 
      "case of graphs", 
      "problem", 
      "finite graphs", 
      "edge-labeled graphs", 
      "BPP", 
      "general approach", 
      "graph", 
      "undecidability", 
      "bisimilarity", 
      "vertices", 
      "tutorial", 
      "decidability", 
      "machine"
    ], 
    "name": "Techniques for Decidability and Undecidability of Bisimilarity", 
    "pagination": "30-45", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1027984004"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-48320-9_5"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-48320-9_5", 
      "https://app.dimensions.ai/details/publication/pub.1027984004"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:42", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_180.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-48320-9_5"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/3-540-48320-9_5'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/3-540-48320-9_5'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-48320-9_5'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-48320-9_5'


 

This table displays all metadata directly associated to this object as RDF triples.

96 TRIPLES      23 PREDICATES      47 URIs      40 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-48320-9_5 schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author N907ce009e36644cb93e3ab3333b6dfdb
4 schema:datePublished 1999
5 schema:datePublishedReg 1999-01-01
6 schema:description In this tutorial we describe general approaches to deciding bisimilarity between vertices of (infinite) directed edge-labelled graphs. The approaches are based on a systematic search following the definition of bisimilarity. We outline (in decreasing levels of detail) how the search is modified to solve the problem for finite graphs, BPP graphs, BPA graphs, normed PA graphs, and normed PDA graphs. We complete this by showing the technique used in the case of graphs generated by onecounter machines. Finally, we demonstrate a general reduction strategy for proving undecidability, which we apply in the case of graphs generated by state-extended BPP (a restricted form of labelled Petri nets).
7 schema:editor Nb49d872e2d64497197b9cdd9708dd253
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nc10ec9bfcb7c49008c02a4666efa2fa6
12 schema:keywords BPP
13 approach
14 bisimilarity
15 case of graphs
16 cases
17 decidability
18 definition
19 edge-labeled graphs
20 finite graphs
21 general approach
22 graph
23 machine
24 problem
25 reduction strategies
26 search
27 strategies
28 systematic search
29 technique
30 tutorial
31 undecidability
32 vertices
33 schema:name Techniques for Decidability and Undecidability of Bisimilarity
34 schema:pagination 30-45
35 schema:productId N8bd9f7c362cf45a5a8f4cf598c4dec5f
36 Nc0cabddfb42c4b8a860acc613e13d2ca
37 schema:publisher N3832174441f34d8784a9d3442eba2de1
38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027984004
39 https://doi.org/10.1007/3-540-48320-9_5
40 schema:sdDatePublished 2022-05-20T07:42
41 schema:sdLicense https://scigraph.springernature.com/explorer/license/
42 schema:sdPublisher Nd84395f2bb1741bbb3bfc6df73235c0e
43 schema:url https://doi.org/10.1007/3-540-48320-9_5
44 sgo:license sg:explorer/license/
45 sgo:sdDataset chapters
46 rdf:type schema:Chapter
47 N25e84f815d384e7587404587f4aea192 schema:familyName Mauw
48 schema:givenName Sjouke
49 rdf:type schema:Person
50 N3832174441f34d8784a9d3442eba2de1 schema:name Springer Nature
51 rdf:type schema:Organisation
52 N499b656641fb43a9b638913d21f040bf rdf:first sg:person.010425236217.29
53 rdf:rest rdf:nil
54 N70ff2bf5ae10434d83a73bd0c70bf1d4 rdf:first N25e84f815d384e7587404587f4aea192
55 rdf:rest rdf:nil
56 N8bd9f7c362cf45a5a8f4cf598c4dec5f schema:name doi
57 schema:value 10.1007/3-540-48320-9_5
58 rdf:type schema:PropertyValue
59 N907ce009e36644cb93e3ab3333b6dfdb rdf:first sg:person.07724710171.43
60 rdf:rest N499b656641fb43a9b638913d21f040bf
61 Nada084067b9443158d11bc9342cba61f schema:familyName Baeten
62 schema:givenName Jos C. M.
63 rdf:type schema:Person
64 Nb49d872e2d64497197b9cdd9708dd253 rdf:first Nada084067b9443158d11bc9342cba61f
65 rdf:rest N70ff2bf5ae10434d83a73bd0c70bf1d4
66 Nc0cabddfb42c4b8a860acc613e13d2ca schema:name dimensions_id
67 schema:value pub.1027984004
68 rdf:type schema:PropertyValue
69 Nc10ec9bfcb7c49008c02a4666efa2fa6 schema:isbn 978-3-540-48320-5
70 978-3-540-66425-3
71 schema:name CONCUR’99 Concurrency Theory
72 rdf:type schema:Book
73 Nd84395f2bb1741bbb3bfc6df73235c0e schema:name Springer Nature - SN SciGraph project
74 rdf:type schema:Organization
75 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
76 schema:name Information and Computing Sciences
77 rdf:type schema:DefinedTerm
78 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
79 schema:name Information Systems
80 rdf:type schema:DefinedTerm
81 sg:person.010425236217.29 schema:affiliation grid-institutes:grid.8993.b
82 schema:familyName Moller
83 schema:givenName Faron
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010425236217.29
85 rdf:type schema:Person
86 sg:person.07724710171.43 schema:affiliation grid-institutes:grid.440850.d
87 schema:familyName Jančar
88 schema:givenName Petr
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07724710171.43
90 rdf:type schema:Person
91 grid-institutes:grid.440850.d schema:alternateName Technical University of Ostrava, Czech Republic
92 schema:name Technical University of Ostrava, Czech Republic
93 rdf:type schema:Organization
94 grid-institutes:grid.8993.b schema:alternateName Uppsala University, Sweden
95 schema:name Uppsala University, Sweden
96 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...