Monadic second order logic and node relations on graphs and trees View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1997

AUTHORS

Roderick Bloem , Joost Engelfriet

ABSTRACT

A formula from monadic second-order (MSO) logic can be used to specify a binary relation on the set of nodes of a tree. It is proved that, equivalently, such a relation can be computed by a finite-state tree-walking automaton, provided the automaton can test MSO properties of the nodes of the tree. For graphs, if a binary relation on the nodes of a graph can be computed by a finite-state graph-walking automaton, then it can be specified by an MSO formula, but, in general, not vice versa. More... »

PAGES

144-161

Book

TITLE

Structures in Logic and Computer Science

ISBN

978-3-540-63246-7
978-3-540-69242-3

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-63246-8_9

DOI

http://dx.doi.org/10.1007/3-540-63246-8_9

DIMENSIONS

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


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/0501", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Ecological Applications", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/05", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Environmental Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Leiden University", 
          "id": "https://www.grid.ac/institutes/grid.5132.5", 
          "name": [
            "Department of Computer Science, Leiden University, P.O.Box 9512, 2300\u00a0RA Leiden, The Netherlands"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bloem", 
        "givenName": "Roderick", 
        "id": "sg:person.011542074410.00", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011542074410.00"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Leiden University", 
          "id": "https://www.grid.ac/institutes/grid.5132.5", 
          "name": [
            "Department of Computer Science, Leiden University, P.O.Box 9512, 2300\u00a0RA Leiden, The Netherlands"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Engelfriet", 
        "givenName": "Joost", 
        "id": "sg:person.014574236321.39", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014574236321.39"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1997", 
    "datePublishedReg": "1997-01-01", 
    "description": "A formula from monadic second-order (MSO) logic can be used to specify a binary relation on the set of nodes of a tree. It is proved that, equivalently, such a relation can be computed by a finite-state tree-walking automaton, provided the automaton can test MSO properties of the nodes of the tree. For graphs, if a binary relation on the nodes of a graph can be computed by a finite-state graph-walking automaton, then it can be specified by an MSO formula, but, in general, not vice versa.", 
    "editor": [
      {
        "familyName": "Mycielski", 
        "givenName": "Jan", 
        "type": "Person"
      }, 
      {
        "familyName": "Rozenberg", 
        "givenName": "Grzegorz", 
        "type": "Person"
      }, 
      {
        "familyName": "Salomaa", 
        "givenName": "Arto", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-63246-8_9", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-63246-7", 
        "978-3-540-69242-3"
      ], 
      "name": "Structures in Logic and Computer Science", 
      "type": "Book"
    }, 
    "name": "Monadic second order logic and node relations on graphs and trees", 
    "pagination": "144-161", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-63246-8_9"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "7797f586cd11b14878c066abeb3193b022bd9a0f55e682c9cdcb31b2c0e929f3"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1025103491"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-63246-8_9", 
      "https://app.dimensions.ai/details/publication/pub.1025103491"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T15:08", 
    "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_8672_00000043.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-63246-8_9"
  }
]
 

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-63246-8_9'

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-63246-8_9'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-63246-8_9'

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-63246-8_9'


 

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

82 TRIPLES      22 PREDICATES      27 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-63246-8_9 schema:about anzsrc-for:05
2 anzsrc-for:0501
3 schema:author N5e7179c9675a41aa8a8c7737a822ae53
4 schema:datePublished 1997
5 schema:datePublishedReg 1997-01-01
6 schema:description A formula from monadic second-order (MSO) logic can be used to specify a binary relation on the set of nodes of a tree. It is proved that, equivalently, such a relation can be computed by a finite-state tree-walking automaton, provided the automaton can test MSO properties of the nodes of the tree. For graphs, if a binary relation on the nodes of a graph can be computed by a finite-state graph-walking automaton, then it can be specified by an MSO formula, but, in general, not vice versa.
7 schema:editor N555090dcb3104d3d9170a681f60dac23
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N422eba2061cb4165b6292fad48ada570
12 schema:name Monadic second order logic and node relations on graphs and trees
13 schema:pagination 144-161
14 schema:productId N079f4483b5ac4f5a87f6cd56765d85dd
15 N5cc0baee8f3a46f283e0c1f217e5e5e8
16 N90ac50a44bd54ea5a65b41f38740a4cf
17 schema:publisher Ncc8201ac8d6e44b4b43959dd5c384d6d
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025103491
19 https://doi.org/10.1007/3-540-63246-8_9
20 schema:sdDatePublished 2019-04-15T15:08
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher N90b400e4e59245e4b9722f14e39a01df
23 schema:url http://link.springer.com/10.1007/3-540-63246-8_9
24 sgo:license sg:explorer/license/
25 sgo:sdDataset chapters
26 rdf:type schema:Chapter
27 N079f4483b5ac4f5a87f6cd56765d85dd schema:name doi
28 schema:value 10.1007/3-540-63246-8_9
29 rdf:type schema:PropertyValue
30 N0ba29d8bc9104a89a75554a6c79b79e2 rdf:first N499ff7f3a1924a30b4a13aa240c125c8
31 rdf:rest rdf:nil
32 N0e43fb124a294cae9137a18e4ebca3f8 schema:familyName Rozenberg
33 schema:givenName Grzegorz
34 rdf:type schema:Person
35 N422eba2061cb4165b6292fad48ada570 schema:isbn 978-3-540-63246-7
36 978-3-540-69242-3
37 schema:name Structures in Logic and Computer Science
38 rdf:type schema:Book
39 N499ff7f3a1924a30b4a13aa240c125c8 schema:familyName Salomaa
40 schema:givenName Arto
41 rdf:type schema:Person
42 N548e83bf39d24c2286f8b82e2d7d7895 rdf:first N0e43fb124a294cae9137a18e4ebca3f8
43 rdf:rest N0ba29d8bc9104a89a75554a6c79b79e2
44 N555090dcb3104d3d9170a681f60dac23 rdf:first N8a4a9b62229a41519525b534162900d4
45 rdf:rest N548e83bf39d24c2286f8b82e2d7d7895
46 N5cc0baee8f3a46f283e0c1f217e5e5e8 schema:name dimensions_id
47 schema:value pub.1025103491
48 rdf:type schema:PropertyValue
49 N5e7179c9675a41aa8a8c7737a822ae53 rdf:first sg:person.011542074410.00
50 rdf:rest Nb98853afbcae4a649dc92355f4f15bda
51 N8a4a9b62229a41519525b534162900d4 schema:familyName Mycielski
52 schema:givenName Jan
53 rdf:type schema:Person
54 N90ac50a44bd54ea5a65b41f38740a4cf schema:name readcube_id
55 schema:value 7797f586cd11b14878c066abeb3193b022bd9a0f55e682c9cdcb31b2c0e929f3
56 rdf:type schema:PropertyValue
57 N90b400e4e59245e4b9722f14e39a01df schema:name Springer Nature - SN SciGraph project
58 rdf:type schema:Organization
59 Nb98853afbcae4a649dc92355f4f15bda rdf:first sg:person.014574236321.39
60 rdf:rest rdf:nil
61 Ncc8201ac8d6e44b4b43959dd5c384d6d schema:location Berlin, Heidelberg
62 schema:name Springer Berlin Heidelberg
63 rdf:type schema:Organisation
64 anzsrc-for:05 schema:inDefinedTermSet anzsrc-for:
65 schema:name Environmental Sciences
66 rdf:type schema:DefinedTerm
67 anzsrc-for:0501 schema:inDefinedTermSet anzsrc-for:
68 schema:name Ecological Applications
69 rdf:type schema:DefinedTerm
70 sg:person.011542074410.00 schema:affiliation https://www.grid.ac/institutes/grid.5132.5
71 schema:familyName Bloem
72 schema:givenName Roderick
73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011542074410.00
74 rdf:type schema:Person
75 sg:person.014574236321.39 schema:affiliation https://www.grid.ac/institutes/grid.5132.5
76 schema:familyName Engelfriet
77 schema:givenName Joost
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014574236321.39
79 rdf:type schema:Person
80 https://www.grid.ac/institutes/grid.5132.5 schema:alternateName Leiden University
81 schema:name Department of Computer Science, Leiden University, P.O.Box 9512, 2300 RA Leiden, The Netherlands
82 rdf:type schema:Organization
 




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


...