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

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 N6a9567eef99e4d33b664f4623cdd886a
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 N51c5f13b878c40dd961e35c69c2f1a9c
21 schema:genre chapter
22 schema:inLanguage en
23 schema:isAccessibleForFree true
24 schema:isPartOf N1d43dd615c2d4909a3e9e762dbdc038a
25 schema:name Tree-Walking Pebble Automata
26 schema:pagination 72-83
27 schema:productId N3e339b304ef042c9bb0754624e263e28
28 N9d1afacffdf64672adea4883876c42d1
29 Na922bad47ccb4b86bf6e3989b1d25f41
30 schema:publisher N44aa9f98e1324d4f981bf71b501463ec
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 N3ea97b56c6b0493a95afcf99a1927fff
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 N01fee60269fb495089d747f70e2a8407 rdf:first N3467097e11fc4cacb8a8948c5566c97a
41 rdf:rest N3d1f5e99989f4ab0b468bfe22c33fa3b
42 N1ad552e757b649bd9b734116f9218f4d rdf:first Ndf4957d9a51742d390e7042c6bb571af
43 rdf:rest N01fee60269fb495089d747f70e2a8407
44 N1d43dd615c2d4909a3e9e762dbdc038a schema:isbn 978-3-642-60207-8
45 978-3-642-64304-0
46 schema:name Jewels are Forever
47 rdf:type schema:Book
48 N3467097e11fc4cacb8a8948c5566c97a schema:familyName Păun
49 schema:givenName Gheorghe
50 rdf:type schema:Person
51 N3d1f5e99989f4ab0b468bfe22c33fa3b rdf:first Nfaf7b330edc34cce8d1c10fcbc92789a
52 rdf:rest rdf:nil
53 N3e339b304ef042c9bb0754624e263e28 schema:name readcube_id
54 schema:value 089cd1f568f090545ff19f82533b78e7ccd5ba9431956bf9d485ae6a0f639b20
55 rdf:type schema:PropertyValue
56 N3ea97b56c6b0493a95afcf99a1927fff schema:name Springer Nature - SN SciGraph project
57 rdf:type schema:Organization
58 N44aa9f98e1324d4f981bf71b501463ec schema:location Berlin, Heidelberg
59 schema:name Springer Berlin Heidelberg
60 rdf:type schema:Organisation
61 N51c5f13b878c40dd961e35c69c2f1a9c rdf:first N8621fb1a547440dc8a4d608aa53fa1dc
62 rdf:rest N1ad552e757b649bd9b734116f9218f4d
63 N6a9567eef99e4d33b664f4623cdd886a rdf:first sg:person.014574236321.39
64 rdf:rest N6d14293da50e4986bc2fa9c5b6092fbb
65 N6d14293da50e4986bc2fa9c5b6092fbb rdf:first sg:person.013762305654.52
66 rdf:rest rdf:nil
67 N8621fb1a547440dc8a4d608aa53fa1dc schema:familyName Karhumäki
68 schema:givenName Juhani
69 rdf:type schema:Person
70 N9d1afacffdf64672adea4883876c42d1 schema:name dimensions_id
71 schema:value pub.1001808103
72 rdf:type schema:PropertyValue
73 Na922bad47ccb4b86bf6e3989b1d25f41 schema:name doi
74 schema:value 10.1007/978-3-642-60207-8_7
75 rdf:type schema:PropertyValue
76 Ndf4957d9a51742d390e7042c6bb571af schema:familyName Maurer
77 schema:givenName Hermann
78 rdf:type schema:Person
79 Nfaf7b330edc34cce8d1c10fcbc92789a schema:familyName Rozenberg
80 schema:givenName Grzegorz
81 rdf:type schema:Person
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)


...