Simulation and Bisimulation over One-Counter Processes View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2000-03-24

AUTHORS

Petr Jančar , Antonín Kučera , Faron Moller

ABSTRACT

We show an effective construction of (a periodicity description of) the maximal simulation relation for a given one-counter net. Then we demonstrate how to reduce simulation problems over one-counter nets to analogous bisimulation problems over one-counter automata. We use this to demonstrate the decidability of various problems, specifically testing regularity and strong regularity of one-counter nets with respect to simulation equivalence, and testing simulation equivalence between a one-counter net and a deterministic pushdown automaton. Various obvious generalisations of these problems are known to be undecidable. More... »

PAGES

334-345

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-46541-3_28

DOI

http://dx.doi.org/10.1007/3-540-46541-3_28

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Technical University Ostrava, Czech Republic", 
          "id": "http://www.grid.ac/institutes/grid.440850.d", 
          "name": [
            "Technical University 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": "Faculty of Informatics MU, Czech Republic", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Faculty of Informatics MU, Czech Republic"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ku\u010dera", 
        "givenName": "Anton\u00edn", 
        "id": "sg:person.012453075541.89", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012453075541.89"
        ], 
        "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": "2000-03-24", 
    "datePublishedReg": "2000-03-24", 
    "description": "We show an effective construction of (a periodicity description of) the maximal simulation relation for a given one-counter net. Then we demonstrate how to reduce simulation problems over one-counter nets to analogous bisimulation problems over one-counter automata. We use this to demonstrate the decidability of various problems, specifically testing regularity and strong regularity of one-counter nets with respect to simulation equivalence, and testing simulation equivalence between a one-counter net and a deterministic pushdown automaton. Various obvious generalisations of these problems are known to be undecidable.", 
    "editor": [
      {
        "familyName": "Reichel", 
        "givenName": "Horst", 
        "type": "Person"
      }, 
      {
        "familyName": "Tison", 
        "givenName": "Sophie", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-46541-3_28", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-67141-1", 
        "978-3-540-46541-6"
      ], 
      "name": "STACS 2000", 
      "type": "Book"
    }, 
    "keywords": [
      "relation", 
      "nets", 
      "problem", 
      "respect", 
      "simulation problems", 
      "bisimulation problem", 
      "regularity", 
      "strong regularity", 
      "simulation equivalence", 
      "equivalence", 
      "obvious generalisation", 
      "process", 
      "effective construction", 
      "simulation relation", 
      "one-counter automata", 
      "automata", 
      "decidability", 
      "generalisation", 
      "simulations", 
      "bisimulation", 
      "one-counter processes", 
      "construction", 
      "one-counter nets"
    ], 
    "name": "Simulation and Bisimulation over One-Counter Processes", 
    "pagination": "334-345", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1024937575"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-46541-3_28"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-46541-3_28", 
      "https://app.dimensions.ai/details/publication/pub.1024937575"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:38", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_142.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-46541-3_28"
  }
]
 

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-46541-3_28'

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-46541-3_28'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-46541-3_28'

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-46541-3_28'


 

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

108 TRIPLES      23 PREDICATES      48 URIs      41 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-46541-3_28 schema:about anzsrc-for:01
2 anzsrc-for:0102
3 schema:author N41a75fde12f94b429ec8fe050eeb3a6a
4 schema:datePublished 2000-03-24
5 schema:datePublishedReg 2000-03-24
6 schema:description We show an effective construction of (a periodicity description of) the maximal simulation relation for a given one-counter net. Then we demonstrate how to reduce simulation problems over one-counter nets to analogous bisimulation problems over one-counter automata. We use this to demonstrate the decidability of various problems, specifically testing regularity and strong regularity of one-counter nets with respect to simulation equivalence, and testing simulation equivalence between a one-counter net and a deterministic pushdown automaton. Various obvious generalisations of these problems are known to be undecidable.
7 schema:editor N6504c5e53e924c9489af8056e2a17eff
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N7eb148e9e997431fa3f95d3f931a306c
12 schema:keywords automata
13 bisimulation
14 bisimulation problem
15 construction
16 decidability
17 effective construction
18 equivalence
19 generalisation
20 nets
21 obvious generalisation
22 one-counter automata
23 one-counter nets
24 one-counter processes
25 problem
26 process
27 regularity
28 relation
29 respect
30 simulation equivalence
31 simulation problems
32 simulation relation
33 simulations
34 strong regularity
35 schema:name Simulation and Bisimulation over One-Counter Processes
36 schema:pagination 334-345
37 schema:productId N370363f52bfd4264b918a2139afc7010
38 Nfb31216e15fe44f5841baa9671f92933
39 schema:publisher Nee53353d6cff4b3a90e4898ea3371731
40 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024937575
41 https://doi.org/10.1007/3-540-46541-3_28
42 schema:sdDatePublished 2022-05-10T10:38
43 schema:sdLicense https://scigraph.springernature.com/explorer/license/
44 schema:sdPublisher Nb917db2fdf8947d99cd923c115228bc7
45 schema:url https://doi.org/10.1007/3-540-46541-3_28
46 sgo:license sg:explorer/license/
47 sgo:sdDataset chapters
48 rdf:type schema:Chapter
49 N370363f52bfd4264b918a2139afc7010 schema:name doi
50 schema:value 10.1007/3-540-46541-3_28
51 rdf:type schema:PropertyValue
52 N3e6fce6b0336449aba10eb30a9403e22 schema:familyName Reichel
53 schema:givenName Horst
54 rdf:type schema:Person
55 N41a75fde12f94b429ec8fe050eeb3a6a rdf:first sg:person.07724710171.43
56 rdf:rest N62a6d606f668468ab128b14b47d77d68
57 N62a6d606f668468ab128b14b47d77d68 rdf:first sg:person.012453075541.89
58 rdf:rest N6d1bd846fd4b431aaee46ca963c320e3
59 N6504c5e53e924c9489af8056e2a17eff rdf:first N3e6fce6b0336449aba10eb30a9403e22
60 rdf:rest N7c3251aa85784a31945af37b5e059adc
61 N6d1bd846fd4b431aaee46ca963c320e3 rdf:first sg:person.010425236217.29
62 rdf:rest rdf:nil
63 N7c3251aa85784a31945af37b5e059adc rdf:first Nb64b7eb0629f4fb384c6ac84abf8e99e
64 rdf:rest rdf:nil
65 N7eb148e9e997431fa3f95d3f931a306c schema:isbn 978-3-540-46541-6
66 978-3-540-67141-1
67 schema:name STACS 2000
68 rdf:type schema:Book
69 Nb64b7eb0629f4fb384c6ac84abf8e99e schema:familyName Tison
70 schema:givenName Sophie
71 rdf:type schema:Person
72 Nb917db2fdf8947d99cd923c115228bc7 schema:name Springer Nature - SN SciGraph project
73 rdf:type schema:Organization
74 Nee53353d6cff4b3a90e4898ea3371731 schema:name Springer Nature
75 rdf:type schema:Organisation
76 Nfb31216e15fe44f5841baa9671f92933 schema:name dimensions_id
77 schema:value pub.1024937575
78 rdf:type schema:PropertyValue
79 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
80 schema:name Mathematical Sciences
81 rdf:type schema:DefinedTerm
82 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
83 schema:name Applied Mathematics
84 rdf:type schema:DefinedTerm
85 sg:person.010425236217.29 schema:affiliation grid-institutes:grid.8993.b
86 schema:familyName Moller
87 schema:givenName Faron
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010425236217.29
89 rdf:type schema:Person
90 sg:person.012453075541.89 schema:affiliation grid-institutes:None
91 schema:familyName Kučera
92 schema:givenName Antonín
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012453075541.89
94 rdf:type schema:Person
95 sg:person.07724710171.43 schema:affiliation grid-institutes:grid.440850.d
96 schema:familyName Jančar
97 schema:givenName Petr
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07724710171.43
99 rdf:type schema:Person
100 grid-institutes:None schema:alternateName Faculty of Informatics MU, Czech Republic
101 schema:name Faculty of Informatics MU, Czech Republic
102 rdf:type schema:Organization
103 grid-institutes:grid.440850.d schema:alternateName Technical University Ostrava, Czech Republic
104 schema:name Technical University Ostrava, Czech Republic
105 rdf:type schema:Organization
106 grid-institutes:grid.8993.b schema:alternateName Uppsala University, Sweden
107 schema:name Uppsala University, Sweden
108 rdf:type schema:Organization
 




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


...