A Practical Simulation Result for Two-Way Pushdown Automata View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2016

AUTHORS

Robert Glück

ABSTRACT

The simulation of two-way deterministic and nondeterministic pushdown automata is revisited. A uniform algorithm presented herein decides on a random-access machine in linear time resp. cubic time whether a given pushdown automaton accepts a word, while the actual run of the automaton may take exponential time. The algorithm is practical since it only explores reachable configurations, simulates a class of quasi-deterministic decision problems in linear time even if the pushdown automaton is nondeterministic, and iterates over a simple work list. This is an improvement over previous simulation algorithms. More... »

PAGES

113-124

Book

TITLE

Implementation and Application of Automata

ISBN

978-3-319-40945-0
978-3-319-40946-7

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-40946-7_10

DOI

http://dx.doi.org/10.1007/978-3-319-40946-7_10

DIMENSIONS

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


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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Copenhagen", 
          "id": "https://www.grid.ac/institutes/grid.5254.6", 
          "name": [
            "DIKU, Department of Computer Science, University of Copenhagen"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gl\u00fcck", 
        "givenName": "Robert", 
        "id": "sg:person.010754010217.31", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010754010217.31"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1003866047", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-0-387-68954-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003866047", 
          "https://doi.org/10.1007/978-0-387-68954-8"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-0-387-68954-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003866047", 
          "https://doi.org/10.1007/978-0-387-68954-8"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/spe.1086", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005085336"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-51237-3_11", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007169098", 
          "https://doi.org/10.1007/3-540-51237-3_11"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/963778.963784", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010449995"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(83)90124-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012264779"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0019-9958(68)91087-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013914005"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/321623.321625", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014684553"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4757-1885-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017979460", 
          "https://doi.org/10.1007/978-1-4757-1885-0"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4757-1885-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017979460", 
          "https://doi.org/10.1007/978-1-4757-1885-0"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(77)90022-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033910504"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0019-9958(85)80024-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041416714"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-41579-6_11", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044803080", 
          "https://doi.org/10.1007/978-3-319-41579-6_11"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0206024", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841363"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.4204/eptcs.129.15", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1072354786"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2016", 
    "datePublishedReg": "2016-01-01", 
    "description": "The simulation of two-way deterministic and nondeterministic pushdown automata is revisited. A uniform algorithm presented herein decides on a random-access machine in linear time resp. cubic time whether a given pushdown automaton accepts a word, while the actual run of the automaton may take exponential time. The algorithm is practical since it only explores reachable configurations, simulates a class of quasi-deterministic decision problems in linear time even if the pushdown automaton is nondeterministic, and iterates over a simple work list. This is an improvement over previous simulation algorithms.", 
    "editor": [
      {
        "familyName": "Han", 
        "givenName": "Yo-Sub", 
        "type": "Person"
      }, 
      {
        "familyName": "Salomaa", 
        "givenName": "Kai", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-40946-7_10", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-40945-0", 
        "978-3-319-40946-7"
      ], 
      "name": "Implementation and Application of Automata", 
      "type": "Book"
    }, 
    "name": "A Practical Simulation Result for Two-Way Pushdown Automata", 
    "pagination": "113-124", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-40946-7_10"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "db50638768910c9ac3c0ef7749b43f340e8599e39b6f6cbd7fdd1cd692844c95"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1046041225"
        ]
      }
    ], 
    "publisher": {
      "location": "Cham", 
      "name": "Springer International Publishing", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-40946-7_10", 
      "https://app.dimensions.ai/details/publication/pub.1046041225"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T19:11", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8684_00000271.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-319-40946-7_10"
  }
]
 

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-319-40946-7_10'

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-319-40946-7_10'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-40946-7_10'

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-319-40946-7_10'


 

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

115 TRIPLES      23 PREDICATES      41 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-40946-7_10 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N6541daf3e6d646ce88360e64f6aaa326
4 schema:citation sg:pub.10.1007/3-540-51237-3_11
5 sg:pub.10.1007/978-0-387-68954-8
6 sg:pub.10.1007/978-1-4757-1885-0
7 sg:pub.10.1007/978-3-319-41579-6_11
8 https://app.dimensions.ai/details/publication/pub.1003866047
9 https://doi.org/10.1002/spe.1086
10 https://doi.org/10.1016/0020-0190(77)90022-9
11 https://doi.org/10.1016/0020-0190(83)90124-2
12 https://doi.org/10.1016/s0019-9958(68)91087-5
13 https://doi.org/10.1016/s0019-9958(85)80024-3
14 https://doi.org/10.1137/0206024
15 https://doi.org/10.1145/321623.321625
16 https://doi.org/10.1145/963778.963784
17 https://doi.org/10.4204/eptcs.129.15
18 schema:datePublished 2016
19 schema:datePublishedReg 2016-01-01
20 schema:description The simulation of two-way deterministic and nondeterministic pushdown automata is revisited. A uniform algorithm presented herein decides on a random-access machine in linear time resp. cubic time whether a given pushdown automaton accepts a word, while the actual run of the automaton may take exponential time. The algorithm is practical since it only explores reachable configurations, simulates a class of quasi-deterministic decision problems in linear time even if the pushdown automaton is nondeterministic, and iterates over a simple work list. This is an improvement over previous simulation algorithms.
21 schema:editor N511ade0b6d6f4178b8bb310556fd7a4d
22 schema:genre chapter
23 schema:inLanguage en
24 schema:isAccessibleForFree false
25 schema:isPartOf N34ec0f2e87364043adf72de01b6ec42d
26 schema:name A Practical Simulation Result for Two-Way Pushdown Automata
27 schema:pagination 113-124
28 schema:productId N5a656b49b4274e669faed4628c9df27b
29 N68b7bf575d77469c872a32c2501d1734
30 N84df5c21977d44cfa099cce4e0993976
31 schema:publisher Nbc0b6c9b409949f3b34b961b2db46144
32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046041225
33 https://doi.org/10.1007/978-3-319-40946-7_10
34 schema:sdDatePublished 2019-04-15T19:11
35 schema:sdLicense https://scigraph.springernature.com/explorer/license/
36 schema:sdPublisher N187b31d05ac14acfbbd6767eaff90e3e
37 schema:url http://link.springer.com/10.1007/978-3-319-40946-7_10
38 sgo:license sg:explorer/license/
39 sgo:sdDataset chapters
40 rdf:type schema:Chapter
41 N05733fb74ae44e8fb833e42edff91083 rdf:first Nc203c2d85dc84856b7e6f6380d70803f
42 rdf:rest rdf:nil
43 N187b31d05ac14acfbbd6767eaff90e3e schema:name Springer Nature - SN SciGraph project
44 rdf:type schema:Organization
45 N34ec0f2e87364043adf72de01b6ec42d schema:isbn 978-3-319-40945-0
46 978-3-319-40946-7
47 schema:name Implementation and Application of Automata
48 rdf:type schema:Book
49 N511ade0b6d6f4178b8bb310556fd7a4d rdf:first Ne8a1d02c584d4231aa61f3ba3cf6abfe
50 rdf:rest N05733fb74ae44e8fb833e42edff91083
51 N5a656b49b4274e669faed4628c9df27b schema:name doi
52 schema:value 10.1007/978-3-319-40946-7_10
53 rdf:type schema:PropertyValue
54 N6541daf3e6d646ce88360e64f6aaa326 rdf:first sg:person.010754010217.31
55 rdf:rest rdf:nil
56 N68b7bf575d77469c872a32c2501d1734 schema:name dimensions_id
57 schema:value pub.1046041225
58 rdf:type schema:PropertyValue
59 N84df5c21977d44cfa099cce4e0993976 schema:name readcube_id
60 schema:value db50638768910c9ac3c0ef7749b43f340e8599e39b6f6cbd7fdd1cd692844c95
61 rdf:type schema:PropertyValue
62 Nbc0b6c9b409949f3b34b961b2db46144 schema:location Cham
63 schema:name Springer International Publishing
64 rdf:type schema:Organisation
65 Nc203c2d85dc84856b7e6f6380d70803f schema:familyName Salomaa
66 schema:givenName Kai
67 rdf:type schema:Person
68 Ne8a1d02c584d4231aa61f3ba3cf6abfe schema:familyName Han
69 schema:givenName Yo-Sub
70 rdf:type schema:Person
71 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
72 schema:name Information and Computing Sciences
73 rdf:type schema:DefinedTerm
74 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
75 schema:name Artificial Intelligence and Image Processing
76 rdf:type schema:DefinedTerm
77 sg:person.010754010217.31 schema:affiliation https://www.grid.ac/institutes/grid.5254.6
78 schema:familyName Glück
79 schema:givenName Robert
80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010754010217.31
81 rdf:type schema:Person
82 sg:pub.10.1007/3-540-51237-3_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007169098
83 https://doi.org/10.1007/3-540-51237-3_11
84 rdf:type schema:CreativeWork
85 sg:pub.10.1007/978-0-387-68954-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003866047
86 https://doi.org/10.1007/978-0-387-68954-8
87 rdf:type schema:CreativeWork
88 sg:pub.10.1007/978-1-4757-1885-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017979460
89 https://doi.org/10.1007/978-1-4757-1885-0
90 rdf:type schema:CreativeWork
91 sg:pub.10.1007/978-3-319-41579-6_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044803080
92 https://doi.org/10.1007/978-3-319-41579-6_11
93 rdf:type schema:CreativeWork
94 https://app.dimensions.ai/details/publication/pub.1003866047 schema:CreativeWork
95 https://doi.org/10.1002/spe.1086 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005085336
96 rdf:type schema:CreativeWork
97 https://doi.org/10.1016/0020-0190(77)90022-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033910504
98 rdf:type schema:CreativeWork
99 https://doi.org/10.1016/0020-0190(83)90124-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012264779
100 rdf:type schema:CreativeWork
101 https://doi.org/10.1016/s0019-9958(68)91087-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013914005
102 rdf:type schema:CreativeWork
103 https://doi.org/10.1016/s0019-9958(85)80024-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041416714
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1137/0206024 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841363
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1145/321623.321625 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014684553
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1145/963778.963784 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010449995
110 rdf:type schema:CreativeWork
111 https://doi.org/10.4204/eptcs.129.15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072354786
112 rdf:type schema:CreativeWork
113 https://www.grid.ac/institutes/grid.5254.6 schema:alternateName University of Copenhagen
114 schema:name DIKU, Department of Computer Science, University of Copenhagen
115 rdf:type schema:Organization
 




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


...