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 Σ 2 P =NPNP: 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(n 13) 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(n 4 v) 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

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bfb0014997

DOI

http://dx.doi.org/10.1007/bfb0014997

DIMENSIONS

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


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 \u03a3 2 P =NPNP: 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(n 13) 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(n 4 v) 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/bfb0014997", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-58329-5"
      ], 
      "name": "CONCUR '94: Concurrency Theory", 
      "type": "Book"
    }, 
    "keywords": [
      "polynomial time", 
      "efficient polynomial algorithms", 
      "context-free processes", 
      "such algorithms", 
      "proof of equivalence", 
      "corresponding grammar", 
      "polynomial algorithm", 
      "fast 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", 
      "NPNP", 
      "description", 
      "equivalence", 
      "number", 
      "distance", 
      "short distances", 
      "state", 
      "size", 
      "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.1022567229"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bfb0014997"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/bfb0014997", 
      "https://app.dimensions.ai/details/publication/pub.1022567229"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:46", 
    "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_329.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/bfb0014997"
  }
]
 

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/bfb0014997'

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/bfb0014997'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bfb0014997'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bfb0014997'


 

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

115 TRIPLES      23 PREDICATES      70 URIs      63 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bfb0014997 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N7d593963d48a4a189b70db46b7a43cfc
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 Σ 2 P =NPNP: 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(n 13) 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(n 4 v) 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 Nda5cfb8ca8404de2937d16caad3112f2
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N7563e2ee4174426aa2097e68674a2d04
12 schema:keywords Hirshfeld
13 Huynh
14 Jerrum
15 Moller
16 NPNP
17 NPs
18 Tian
19 algorithm
20 bisimilarity
21 bisimulation equivalence
22 context-free processes
23 corresponding grammar
24 description
25 deterministic algorithm
26 distance
27 efficient polynomial algorithms
28 equivalence
29 example
30 exponential time
31 fast algorithm
32 grammar
33 moderate size
34 norms
35 number
36 number of symbols
37 oracle
38 paper
39 polynomial algorithm
40 polynomial time
41 practice
42 problem
43 process
44 proof
45 proof of equivalence
46 questions
47 short distances
48 short words
49 size
50 state
51 such algorithms
52 symbols
53 technique
54 time
55 words
56 schema:name A fast algorithm for deciding bisimilarity of normed context-free processes
57 schema:pagination 48-63
58 schema:productId N36a58a94527845a6b303051de19b325a
59 Naae9970c94254dbab7ee83beb852bb68
60 schema:publisher Nfc61d17ea1c546829e828be851f6ed41
61 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022567229
62 https://doi.org/10.1007/bfb0014997
63 schema:sdDatePublished 2022-05-20T07:46
64 schema:sdLicense https://scigraph.springernature.com/explorer/license/
65 schema:sdPublisher N2bae94cf124649c89ccb0e415d997fa9
66 schema:url https://doi.org/10.1007/bfb0014997
67 sgo:license sg:explorer/license/
68 sgo:sdDataset chapters
69 rdf:type schema:Chapter
70 N034916afc79d451fa09cfd08b5688823 rdf:first N12b768f1ff844571a9328bcef77bd43a
71 rdf:rest rdf:nil
72 N12b768f1ff844571a9328bcef77bd43a schema:familyName Parrow
73 schema:givenName Joachim
74 rdf:type schema:Person
75 N28cf9988addc4beb9a852fe79a287c87 rdf:first sg:person.010425236217.29
76 rdf:rest rdf:nil
77 N2bae94cf124649c89ccb0e415d997fa9 schema:name Springer Nature - SN SciGraph project
78 rdf:type schema:Organization
79 N36a58a94527845a6b303051de19b325a schema:name dimensions_id
80 schema:value pub.1022567229
81 rdf:type schema:PropertyValue
82 N7563e2ee4174426aa2097e68674a2d04 schema:isbn 978-3-540-58329-5
83 schema:name CONCUR '94: Concurrency Theory
84 rdf:type schema:Book
85 N7d593963d48a4a189b70db46b7a43cfc rdf:first sg:person.013456371571.52
86 rdf:rest N28cf9988addc4beb9a852fe79a287c87
87 Naae9970c94254dbab7ee83beb852bb68 schema:name doi
88 schema:value 10.1007/bfb0014997
89 rdf:type schema:PropertyValue
90 Nda5cfb8ca8404de2937d16caad3112f2 rdf:first Nfb998eb6d97c418aa30d40f84f6bda4c
91 rdf:rest N034916afc79d451fa09cfd08b5688823
92 Nfb998eb6d97c418aa30d40f84f6bda4c schema:familyName Jonsson
93 schema:givenName Bengt
94 rdf:type schema:Person
95 Nfc61d17ea1c546829e828be851f6ed41 schema:name Springer Nature
96 rdf:type schema:Organisation
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)


...