Simulation Problems for One-Counter Machine View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1999

AUTHORS

Petr Jančar , Faron Moller , 1Zdeněk Sawa

ABSTRACT

We consider decidability questions for simulation preorder (and equivalence) for processes generated by one-counter machines. We sketch a proof of decidability in the case when testing for zero is not possible, and demonstrate the undecidability in the general case.

PAGES

404-413

Book

TITLE

SOFSEM’99: Theory and Practice of Informatics

ISBN

978-3-540-66694-3
978-3-540-47849-2

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "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"
      }, 
      {
        "familyName": "Sawa", 
        "givenName": "1Zden\u011bk", 
        "id": "sg:person.016412231345.81", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016412231345.81"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1999", 
    "datePublishedReg": "1999-01-01", 
    "description": "We consider decidability questions for simulation preorder (and equivalence) for processes generated by one-counter machines. We sketch a proof of decidability in the case when testing for zero is not possible, and demonstrate the undecidability in the general case.", 
    "editor": [
      {
        "familyName": "Pavelka", 
        "givenName": "Jan", 
        "type": "Person"
      }, 
      {
        "familyName": "Tel", 
        "givenName": "Gerard", 
        "type": "Person"
      }, 
      {
        "familyName": "Barto\u0161ek", 
        "givenName": "Miroslav", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-47849-3_28", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-66694-3", 
        "978-3-540-47849-2"
      ], 
      "name": "SOFSEM\u201999: Theory and Practice of Informatics", 
      "type": "Book"
    }, 
    "keywords": [
      "one-counter machines", 
      "simulation preorder", 
      "simulation problems", 
      "proof of decidability", 
      "machine", 
      "general case", 
      "decidability questions", 
      "decidability", 
      "preorder", 
      "undecidability", 
      "proof", 
      "process", 
      "cases", 
      "questions", 
      "problem"
    ], 
    "name": "Simulation Problems for One-Counter Machine", 
    "pagination": "404-413", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1037652807"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-47849-3_28"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-47849-3_28", 
      "https://app.dimensions.ai/details/publication/pub.1037652807"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:49", 
    "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_7.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-47849-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-47849-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-47849-3_28'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-47849-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-47849-3_28'


 

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

101 TRIPLES      23 PREDICATES      41 URIs      34 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-47849-3_28 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N682300b7efb34d5d9d55323a8c258875
4 schema:datePublished 1999
5 schema:datePublishedReg 1999-01-01
6 schema:description We consider decidability questions for simulation preorder (and equivalence) for processes generated by one-counter machines. We sketch a proof of decidability in the case when testing for zero is not possible, and demonstrate the undecidability in the general case.
7 schema:editor Nbaf95ffa03ca464c964961447062d587
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nef47dd6aaa1449a3940913cc9233246d
12 schema:keywords cases
13 decidability
14 decidability questions
15 general case
16 machine
17 one-counter machines
18 preorder
19 problem
20 process
21 proof
22 proof of decidability
23 questions
24 simulation preorder
25 simulation problems
26 undecidability
27 schema:name Simulation Problems for One-Counter Machine
28 schema:pagination 404-413
29 schema:productId Nf02dfb66ef27497fba9a2f06abfcbc7d
30 Nf624abc42e4a47a68c574a6d879edb19
31 schema:publisher Na68ac15fed0c48a796c92708d5b3512b
32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037652807
33 https://doi.org/10.1007/3-540-47849-3_28
34 schema:sdDatePublished 2022-05-20T07:49
35 schema:sdLicense https://scigraph.springernature.com/explorer/license/
36 schema:sdPublisher Ndca2cd138f304b5bbb73e1ba3d099119
37 schema:url https://doi.org/10.1007/3-540-47849-3_28
38 sgo:license sg:explorer/license/
39 sgo:sdDataset chapters
40 rdf:type schema:Chapter
41 N0adef99d49884307a4ae873a49c5fa89 rdf:first sg:person.016412231345.81
42 rdf:rest rdf:nil
43 N613f5a0f925c4a238f3efd4cbd1ec50d schema:familyName Bartošek
44 schema:givenName Miroslav
45 rdf:type schema:Person
46 N682300b7efb34d5d9d55323a8c258875 rdf:first sg:person.07724710171.43
47 rdf:rest N921eb8dd1390429babf91dc64a3dbea3
48 N7c25ac991e4d4172a7b02ddb2ba24ece rdf:first N613f5a0f925c4a238f3efd4cbd1ec50d
49 rdf:rest rdf:nil
50 N837d2bf7559f4f8a9157fa960b5e1db1 rdf:first N96adbc4f9e964a2998c47265946f9860
51 rdf:rest N7c25ac991e4d4172a7b02ddb2ba24ece
52 N921eb8dd1390429babf91dc64a3dbea3 rdf:first sg:person.010425236217.29
53 rdf:rest N0adef99d49884307a4ae873a49c5fa89
54 N96adbc4f9e964a2998c47265946f9860 schema:familyName Tel
55 schema:givenName Gerard
56 rdf:type schema:Person
57 Na68ac15fed0c48a796c92708d5b3512b schema:name Springer Nature
58 rdf:type schema:Organisation
59 Nbaf95ffa03ca464c964961447062d587 rdf:first Ne1e661ed66014867a9c1a8a11ca196f3
60 rdf:rest N837d2bf7559f4f8a9157fa960b5e1db1
61 Ndca2cd138f304b5bbb73e1ba3d099119 schema:name Springer Nature - SN SciGraph project
62 rdf:type schema:Organization
63 Ne1e661ed66014867a9c1a8a11ca196f3 schema:familyName Pavelka
64 schema:givenName Jan
65 rdf:type schema:Person
66 Nef47dd6aaa1449a3940913cc9233246d schema:isbn 978-3-540-47849-2
67 978-3-540-66694-3
68 schema:name SOFSEM’99: Theory and Practice of Informatics
69 rdf:type schema:Book
70 Nf02dfb66ef27497fba9a2f06abfcbc7d schema:name dimensions_id
71 schema:value pub.1037652807
72 rdf:type schema:PropertyValue
73 Nf624abc42e4a47a68c574a6d879edb19 schema:name doi
74 schema:value 10.1007/3-540-47849-3_28
75 rdf:type schema:PropertyValue
76 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
77 schema:name Information and Computing Sciences
78 rdf:type schema:DefinedTerm
79 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
80 schema:name Artificial Intelligence and Image Processing
81 rdf:type schema:DefinedTerm
82 sg:person.010425236217.29 schema:affiliation grid-institutes:grid.8993.b
83 schema:familyName Moller
84 schema:givenName Faron
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010425236217.29
86 rdf:type schema:Person
87 sg:person.016412231345.81 schema:familyName Sawa
88 schema:givenName 1Zdeněk
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016412231345.81
90 rdf:type schema:Person
91 sg:person.07724710171.43 schema:affiliation grid-institutes:grid.440850.d
92 schema:familyName Jančar
93 schema:givenName Petr
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07724710171.43
95 rdf:type schema:Person
96 grid-institutes:grid.440850.d schema:alternateName Technical University of Ostrava, Czech Republic
97 schema:name Technical University of Ostrava, Czech Republic
98 rdf:type schema:Organization
99 grid-institutes:grid.8993.b schema:alternateName Uppsala University, Sweden
100 schema:name Uppsala University, Sweden
101 rdf:type schema:Organization
 




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


...