Tree-Walking Pebble Automata View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1999

AUTHORS

Joost Engelfriet , Hendrik Jan Hoogeboom

ABSTRACT

The tree languages accepted by (finite state) tree-walking automata are known to form a subclass of the regular tree languages which is not known to be proper. They include all locally first-order definable tree languages. We allow the tree-walking automaton to use a finite number of pebbles, which have to be dropped and lifted in a nested fashion. The class of tree languages accepted by these tree-walking pebble automata contains all first-order definable tree languages and is still included in the class of regular tree languages. It also contains all deterministic top-down recognizable tree languages. More... »

PAGES

72-83

References to SciGraph publications

Book

TITLE

Jewels are Forever

ISBN

978-3-642-64304-0
978-3-642-60207-8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-60207-8_7

DOI

http://dx.doi.org/10.1007/978-3-642-60207-8_7

DIMENSIONS

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


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/2004", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Linguistics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/20", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Language, Communication and Culture", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "familyName": "Engelfriet", 
        "givenName": "Joost", 
        "id": "sg:person.014574236321.39", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014574236321.39"
        ], 
        "type": "Person"
      }, 
      {
        "familyName": "Hoogeboom", 
        "givenName": "Hendrik Jan", 
        "id": "sg:person.013762305654.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013762305654.52"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/s0022-0000(70)80041-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006764898"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0019-9958(81)90438-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020821867"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-63246-8_9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025103491", 
          "https://doi.org/10.1007/3-540-63246-8_9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0304-3975(96)00119-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026184128"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0022-0000(80)90058-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028307536"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/malq.19600060105", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1029582399"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01691346", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038809008", 
          "https://doi.org/10.1007/bf01691346"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01691346", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038809008", 
          "https://doi.org/10.1007/bf01691346"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01691346", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038809008", 
          "https://doi.org/10.1007/bf01691346"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/s0002-9947-1961-0139530-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043986220"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0019-9958(71)90706-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046403722"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1147/rd.32.0114", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1063181561"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1147/rd.32.0198", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1063181574"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.1978.18", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086164600"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/focs.1967.6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086169463"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1999", 
    "datePublishedReg": "1999-01-01", 
    "description": "The tree languages accepted by (finite state) tree-walking automata are known to form a subclass of the regular tree languages which is not known to be proper. They include all locally first-order definable tree languages. We allow the tree-walking automaton to use a finite number of pebbles, which have to be dropped and lifted in a nested fashion. The class of tree languages accepted by these tree-walking pebble automata contains all first-order definable tree languages and is still included in the class of regular tree languages. It also contains all deterministic top-down recognizable tree languages.", 
    "editor": [
      {
        "familyName": "Karhum\u00e4ki", 
        "givenName": "Juhani", 
        "type": "Person"
      }, 
      {
        "familyName": "Maurer", 
        "givenName": "Hermann", 
        "type": "Person"
      }, 
      {
        "familyName": "P\u0103un", 
        "givenName": "Gheorghe", 
        "type": "Person"
      }, 
      {
        "familyName": "Rozenberg", 
        "givenName": "Grzegorz", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-60207-8_7", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-64304-0", 
        "978-3-642-60207-8"
      ], 
      "name": "Jewels are Forever", 
      "type": "Book"
    }, 
    "name": "Tree-Walking Pebble Automata", 
    "pagination": "72-83", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1001808103"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-60207-8_7"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "089cd1f568f090545ff19f82533b78e7ccd5ba9431956bf9d485ae6a0f639b20"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-60207-8_7", 
      "https://app.dimensions.ai/details/publication/pub.1001808103"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T09:17", 
    "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/0000000371_0000000371/records_130817_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-642-60207-8_7"
  }
]
 

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-642-60207-8_7'

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-642-60207-8_7'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-60207-8_7'

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-642-60207-8_7'


 

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

123 TRIPLES      23 PREDICATES      40 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-60207-8_7 schema:about anzsrc-for:20
2 anzsrc-for:2004
3 schema:author Ne58817d4b13e4e7fac69467bcdfeaf68
4 schema:citation sg:pub.10.1007/3-540-63246-8_9
5 sg:pub.10.1007/bf01691346
6 https://doi.org/10.1002/malq.19600060105
7 https://doi.org/10.1016/0022-0000(80)90058-6
8 https://doi.org/10.1016/s0019-9958(71)90706-6
9 https://doi.org/10.1016/s0019-9958(81)90438-1
10 https://doi.org/10.1016/s0022-0000(70)80041-1
11 https://doi.org/10.1016/s0304-3975(96)00119-3
12 https://doi.org/10.1090/s0002-9947-1961-0139530-9
13 https://doi.org/10.1109/focs.1967.6
14 https://doi.org/10.1109/sfcs.1978.18
15 https://doi.org/10.1147/rd.32.0114
16 https://doi.org/10.1147/rd.32.0198
17 schema:datePublished 1999
18 schema:datePublishedReg 1999-01-01
19 schema:description The tree languages accepted by (finite state) tree-walking automata are known to form a subclass of the regular tree languages which is not known to be proper. They include all locally first-order definable tree languages. We allow the tree-walking automaton to use a finite number of pebbles, which have to be dropped and lifted in a nested fashion. The class of tree languages accepted by these tree-walking pebble automata contains all first-order definable tree languages and is still included in the class of regular tree languages. It also contains all deterministic top-down recognizable tree languages.
20 schema:editor N4a329c6e48a6474dad2a05f30a5e3f7c
21 schema:genre chapter
22 schema:inLanguage en
23 schema:isAccessibleForFree true
24 schema:isPartOf N8fbf5b1b05a348eeaaeeb4d696e667b7
25 schema:name Tree-Walking Pebble Automata
26 schema:pagination 72-83
27 schema:productId N1e22430c2d52489490cc4979150cb8ca
28 N4a2f847dad2e488f86d1fa70b9d15af8
29 Nde5d40d8c8d04545b3c954b35aff6981
30 schema:publisher N13fbef3914774150949a9c35a441bec7
31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001808103
32 https://doi.org/10.1007/978-3-642-60207-8_7
33 schema:sdDatePublished 2019-04-16T09:17
34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
35 schema:sdPublisher N95014d458aae464f80ad3d67386b5990
36 schema:url https://link.springer.com/10.1007%2F978-3-642-60207-8_7
37 sgo:license sg:explorer/license/
38 sgo:sdDataset chapters
39 rdf:type schema:Chapter
40 N13fbef3914774150949a9c35a441bec7 schema:location Berlin, Heidelberg
41 schema:name Springer Berlin Heidelberg
42 rdf:type schema:Organisation
43 N1e22430c2d52489490cc4979150cb8ca schema:name readcube_id
44 schema:value 089cd1f568f090545ff19f82533b78e7ccd5ba9431956bf9d485ae6a0f639b20
45 rdf:type schema:PropertyValue
46 N46a3255380964e9aa05c54f2017654ff rdf:first sg:person.013762305654.52
47 rdf:rest rdf:nil
48 N4a2f847dad2e488f86d1fa70b9d15af8 schema:name doi
49 schema:value 10.1007/978-3-642-60207-8_7
50 rdf:type schema:PropertyValue
51 N4a329c6e48a6474dad2a05f30a5e3f7c rdf:first Nb9bdf6e8a3124f81a88b821f92701031
52 rdf:rest N5340b201ced242edbbd48c73e3a15433
53 N5340b201ced242edbbd48c73e3a15433 rdf:first N5fb061391b30456a9680add2d5001972
54 rdf:rest N6d1aec337aba4022805d633a8c520ff1
55 N5fb061391b30456a9680add2d5001972 schema:familyName Maurer
56 schema:givenName Hermann
57 rdf:type schema:Person
58 N6d1aec337aba4022805d633a8c520ff1 rdf:first Nd367a52b193a4ea185e872444271ed38
59 rdf:rest Na69a53ffd7c547c089d0ba43dde4ae95
60 N8fbf5b1b05a348eeaaeeb4d696e667b7 schema:isbn 978-3-642-60207-8
61 978-3-642-64304-0
62 schema:name Jewels are Forever
63 rdf:type schema:Book
64 N95014d458aae464f80ad3d67386b5990 schema:name Springer Nature - SN SciGraph project
65 rdf:type schema:Organization
66 Na69a53ffd7c547c089d0ba43dde4ae95 rdf:first Nc80b749ada5e442caf44709d1df939ca
67 rdf:rest rdf:nil
68 Nb9bdf6e8a3124f81a88b821f92701031 schema:familyName Karhumäki
69 schema:givenName Juhani
70 rdf:type schema:Person
71 Nc80b749ada5e442caf44709d1df939ca schema:familyName Rozenberg
72 schema:givenName Grzegorz
73 rdf:type schema:Person
74 Nd367a52b193a4ea185e872444271ed38 schema:familyName Păun
75 schema:givenName Gheorghe
76 rdf:type schema:Person
77 Nde5d40d8c8d04545b3c954b35aff6981 schema:name dimensions_id
78 schema:value pub.1001808103
79 rdf:type schema:PropertyValue
80 Ne58817d4b13e4e7fac69467bcdfeaf68 rdf:first sg:person.014574236321.39
81 rdf:rest N46a3255380964e9aa05c54f2017654ff
82 anzsrc-for:20 schema:inDefinedTermSet anzsrc-for:
83 schema:name Language, Communication and Culture
84 rdf:type schema:DefinedTerm
85 anzsrc-for:2004 schema:inDefinedTermSet anzsrc-for:
86 schema:name Linguistics
87 rdf:type schema:DefinedTerm
88 sg:person.013762305654.52 schema:familyName Hoogeboom
89 schema:givenName Hendrik Jan
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013762305654.52
91 rdf:type schema:Person
92 sg:person.014574236321.39 schema:familyName Engelfriet
93 schema:givenName Joost
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014574236321.39
95 rdf:type schema:Person
96 sg:pub.10.1007/3-540-63246-8_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025103491
97 https://doi.org/10.1007/3-540-63246-8_9
98 rdf:type schema:CreativeWork
99 sg:pub.10.1007/bf01691346 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038809008
100 https://doi.org/10.1007/bf01691346
101 rdf:type schema:CreativeWork
102 https://doi.org/10.1002/malq.19600060105 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029582399
103 rdf:type schema:CreativeWork
104 https://doi.org/10.1016/0022-0000(80)90058-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028307536
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1016/s0019-9958(71)90706-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046403722
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1016/s0019-9958(81)90438-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020821867
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1016/s0022-0000(70)80041-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006764898
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1016/s0304-3975(96)00119-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026184128
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1090/s0002-9947-1961-0139530-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043986220
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1109/focs.1967.6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086169463
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1109/sfcs.1978.18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086164600
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1147/rd.32.0114 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063181561
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1147/rd.32.0198 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063181574
123 rdf:type schema:CreativeWork
 




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


...