A Fast Algorithm for Deciding Bisimilarity of Normed Context-Free Processes View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1994

AUTHORS

Yoram Hirshfeld , Faron Moller

ABSTRACT

Until recently, algorithms for deciding bisimulation equivalence between normed context-free processes have all been nondeterministic. The optimal such algorithm, due to Huynh and Tian, is in : it guesses a proof of equivalence and validates this proof in polynomial time using oracles freely answering questions which are in NP. Hirshfeld, Jerrum and Moller have since demonstrated that this problem is actually decidable in polynomial time. However, this algorithm is far from being practical, giving a O(n13) algorithm, where n is (roughly) the size of the grammar defining the processes, that is, the number of symbols in its description. In this paper we present a deterministic algorithm which runs in time O(n4v) where v is the norm of the processes being compared, which corresponds to the shortest distance to a terminating state of the process, or the shortest word generated by the corresponding grammar. Though this may be exponential, it still appears to be efficient in practice, when norms are typically of moderate size. Also, the algorithm tends to behave well even when the norm is exponentially large. Furthermore, we believe that the techniques may lead to more efficient polynomial algorithms; indeed we have not been able to find an example for which our optimised algorithm requires exponential time. More... »

PAGES

48-63

Book

TITLE

CONCUR '94: Concurrency Theory

ISBN

978-3-540-58329-5
978-3-540-48654-1

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-48654-1_5

DOI

http://dx.doi.org/10.1007/978-3-540-48654-1_5

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Edinburgh, UK", 
          "id": "http://www.grid.ac/institutes/grid.4305.2", 
          "name": [
            "University of Edinburgh, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hirshfeld", 
        "givenName": "Yoram", 
        "id": "sg:person.013456371571.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013456371571.52"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Edinburgh, UK", 
          "id": "http://www.grid.ac/institutes/grid.4305.2", 
          "name": [
            "University of Edinburgh, UK"
          ], 
          "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": "1994", 
    "datePublishedReg": "1994-01-01", 
    "description": "Until recently, algorithms for deciding bisimulation equivalence between normed context-free processes have all been nondeterministic. The optimal such algorithm, due to Huynh and Tian, is in : it guesses a proof of equivalence and validates this proof in polynomial time using oracles freely answering questions which are in NP. Hirshfeld, Jerrum and Moller have since demonstrated that this problem is actually decidable in polynomial time. However, this algorithm is far from being practical, giving a O(n13) algorithm, where n is (roughly) the size of the grammar defining the processes, that is, the number of symbols in its description. In this paper we present a deterministic algorithm which runs in time O(n4v) where v is the norm of the processes being compared, which corresponds to the shortest distance to a terminating state of the process, or the shortest word generated by the corresponding grammar. Though this may be exponential, it still appears to be efficient in practice, when norms are typically of moderate size. Also, the algorithm tends to behave well even when the norm is exponentially large. Furthermore, we believe that the techniques may lead to more efficient polynomial algorithms; indeed we have not been able to find an example for which our optimised algorithm requires exponential time.", 
    "editor": [
      {
        "familyName": "Jonsson", 
        "givenName": "Bengt", 
        "type": "Person"
      }, 
      {
        "familyName": "Parrow", 
        "givenName": "Joachim", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-48654-1_5", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-58329-5", 
        "978-3-540-48654-1"
      ], 
      "name": "CONCUR '94: Concurrency Theory", 
      "type": "Book"
    }, 
    "keywords": [
      "polynomial time", 
      "efficient polynomial algorithms", 
      "context-free processes", 
      "such algorithms", 
      "proof of equivalence", 
      "corresponding grammar", 
      "fast algorithm", 
      "polynomial algorithm", 
      "number of symbols", 
      "deterministic algorithm", 
      "algorithm", 
      "exponential time", 
      "bisimulation equivalence", 
      "moderate size", 
      "oracle", 
      "grammar", 
      "proof", 
      "NPs", 
      "Jerrum", 
      "bisimilarity", 
      "process", 
      "time", 
      "short words", 
      "technique", 
      "symbols", 
      "words", 
      "example", 
      "description", 
      "equivalence", 
      "number", 
      "distance", 
      "short distances", 
      "size", 
      "state", 
      "norms", 
      "Tian", 
      "practice", 
      "questions", 
      "Moller", 
      "Hirshfeld", 
      "paper", 
      "problem", 
      "Huynh"
    ], 
    "name": "A Fast Algorithm for Deciding Bisimilarity of Normed Context-Free Processes", 
    "pagination": "48-63", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1039825102"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-48654-1_5"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-48654-1_5", 
      "https://app.dimensions.ai/details/publication/pub.1039825102"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:47", 
    "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_384.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-48654-1_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/978-3-540-48654-1_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/978-3-540-48654-1_5'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-48654-1_5'

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

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


 

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

115 TRIPLES      23 PREDICATES      69 URIs      62 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-48654-1_5 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Na19d66c61c204e6daed161260d064e61
4 schema:datePublished 1994
5 schema:datePublishedReg 1994-01-01
6 schema:description Until recently, algorithms for deciding bisimulation equivalence between normed context-free processes have all been nondeterministic. The optimal such algorithm, due to Huynh and Tian, is in : it guesses a proof of equivalence and validates this proof in polynomial time using oracles freely answering questions which are in NP. Hirshfeld, Jerrum and Moller have since demonstrated that this problem is actually decidable in polynomial time. However, this algorithm is far from being practical, giving a O(n13) algorithm, where n is (roughly) the size of the grammar defining the processes, that is, the number of symbols in its description. In this paper we present a deterministic algorithm which runs in time O(n4v) where v is the norm of the processes being compared, which corresponds to the shortest distance to a terminating state of the process, or the shortest word generated by the corresponding grammar. Though this may be exponential, it still appears to be efficient in practice, when norms are typically of moderate size. Also, the algorithm tends to behave well even when the norm is exponentially large. Furthermore, we believe that the techniques may lead to more efficient polynomial algorithms; indeed we have not been able to find an example for which our optimised algorithm requires exponential time.
7 schema:editor N8fc4f21d97e44a22a542904bbcf8a5b6
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N6fbcf0bdcd41497788a2dbb66a9e3a7a
12 schema:keywords Hirshfeld
13 Huynh
14 Jerrum
15 Moller
16 NPs
17 Tian
18 algorithm
19 bisimilarity
20 bisimulation equivalence
21 context-free processes
22 corresponding grammar
23 description
24 deterministic algorithm
25 distance
26 efficient polynomial algorithms
27 equivalence
28 example
29 exponential time
30 fast algorithm
31 grammar
32 moderate size
33 norms
34 number
35 number of symbols
36 oracle
37 paper
38 polynomial algorithm
39 polynomial time
40 practice
41 problem
42 process
43 proof
44 proof of equivalence
45 questions
46 short distances
47 short words
48 size
49 state
50 such algorithms
51 symbols
52 technique
53 time
54 words
55 schema:name A Fast Algorithm for Deciding Bisimilarity of Normed Context-Free Processes
56 schema:pagination 48-63
57 schema:productId Na227f8f3732d475faef567f7a4cb3c31
58 Nd95350b56f164256b987ed1530a17907
59 schema:publisher Nfa9e925fa4d340d5b59b20a49d65a983
60 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039825102
61 https://doi.org/10.1007/978-3-540-48654-1_5
62 schema:sdDatePublished 2022-05-20T07:47
63 schema:sdLicense https://scigraph.springernature.com/explorer/license/
64 schema:sdPublisher N0ed4ccf8f22a44678a4217391d598fa4
65 schema:url https://doi.org/10.1007/978-3-540-48654-1_5
66 sgo:license sg:explorer/license/
67 sgo:sdDataset chapters
68 rdf:type schema:Chapter
69 N040a50c4618843339e0bc1e563e40255 rdf:first sg:person.010425236217.29
70 rdf:rest rdf:nil
71 N0ed4ccf8f22a44678a4217391d598fa4 schema:name Springer Nature - SN SciGraph project
72 rdf:type schema:Organization
73 N1aee2b38843147d9b15b85d498320ddb rdf:first Nd375a21f23eb46349a907a96e156e40e
74 rdf:rest rdf:nil
75 N6fbcf0bdcd41497788a2dbb66a9e3a7a schema:isbn 978-3-540-48654-1
76 978-3-540-58329-5
77 schema:name CONCUR '94: Concurrency Theory
78 rdf:type schema:Book
79 N8fc4f21d97e44a22a542904bbcf8a5b6 rdf:first Nfdfca3decb734e67a66c753e8746213e
80 rdf:rest N1aee2b38843147d9b15b85d498320ddb
81 Na19d66c61c204e6daed161260d064e61 rdf:first sg:person.013456371571.52
82 rdf:rest N040a50c4618843339e0bc1e563e40255
83 Na227f8f3732d475faef567f7a4cb3c31 schema:name doi
84 schema:value 10.1007/978-3-540-48654-1_5
85 rdf:type schema:PropertyValue
86 Nd375a21f23eb46349a907a96e156e40e schema:familyName Parrow
87 schema:givenName Joachim
88 rdf:type schema:Person
89 Nd95350b56f164256b987ed1530a17907 schema:name dimensions_id
90 schema:value pub.1039825102
91 rdf:type schema:PropertyValue
92 Nfa9e925fa4d340d5b59b20a49d65a983 schema:name Springer Nature
93 rdf:type schema:Organisation
94 Nfdfca3decb734e67a66c753e8746213e schema:familyName Jonsson
95 schema:givenName Bengt
96 rdf:type schema:Person
97 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
98 schema:name Information and Computing Sciences
99 rdf:type schema:DefinedTerm
100 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
101 schema:name Computation Theory and Mathematics
102 rdf:type schema:DefinedTerm
103 sg:person.010425236217.29 schema:affiliation grid-institutes:grid.4305.2
104 schema:familyName Moller
105 schema:givenName Faron
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010425236217.29
107 rdf:type schema:Person
108 sg:person.013456371571.52 schema:affiliation grid-institutes:grid.4305.2
109 schema:familyName Hirshfeld
110 schema:givenName Yoram
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013456371571.52
112 rdf:type schema:Person
113 grid-institutes:grid.4305.2 schema:alternateName University of Edinburgh, UK
114 schema:name University of Edinburgh, UK
115 rdf:type schema:Organization
 




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


...