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 N800e482b26384eac98e6fc95629c26e4
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 N2718a8898d6f4d20870676ce2734770f
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N354e018d2a1d4e25a7e3784f78dfc9b8
12 schema:name Monadic second order logic and node relations on graphs and trees
13 schema:pagination 144-161
14 schema:productId N2497380d07da4a50875bead0f5a00a54
15 N2a45c1d62a3a4dc48c3b40fbef578297
16 N970d3956024348d8952de358e569314c
17 schema:publisher N16ed680aab5e44cbaad60c7626ed9d26
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 Nd1abea258d374e3ca8996a4d75126df8
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 N0603461d55744637a0a2cf28e43f9973 rdf:first N09f7a17c14414b2eb365276892405dac
28 rdf:rest rdf:nil
29 N09f7a17c14414b2eb365276892405dac schema:familyName Salomaa
30 schema:givenName Arto
31 rdf:type schema:Person
32 N11cb2cb0c30f4b69802dc3dfc83240ee schema:familyName Mycielski
33 schema:givenName Jan
34 rdf:type schema:Person
35 N16ed680aab5e44cbaad60c7626ed9d26 schema:location Berlin, Heidelberg
36 schema:name Springer Berlin Heidelberg
37 rdf:type schema:Organisation
38 N2497380d07da4a50875bead0f5a00a54 schema:name doi
39 schema:value 10.1007/3-540-63246-8_9
40 rdf:type schema:PropertyValue
41 N2718a8898d6f4d20870676ce2734770f rdf:first N11cb2cb0c30f4b69802dc3dfc83240ee
42 rdf:rest N3f95254f2a0b423eb5b1dff74c326117
43 N28291d6f2d634e279bcc0ff46b5bcbd0 rdf:first sg:person.014574236321.39
44 rdf:rest rdf:nil
45 N2a45c1d62a3a4dc48c3b40fbef578297 schema:name readcube_id
46 schema:value 7797f586cd11b14878c066abeb3193b022bd9a0f55e682c9cdcb31b2c0e929f3
47 rdf:type schema:PropertyValue
48 N354e018d2a1d4e25a7e3784f78dfc9b8 schema:isbn 978-3-540-63246-7
49 978-3-540-69242-3
50 schema:name Structures in Logic and Computer Science
51 rdf:type schema:Book
52 N3f95254f2a0b423eb5b1dff74c326117 rdf:first Nb8fc313111d2470daa3faab756b75624
53 rdf:rest N0603461d55744637a0a2cf28e43f9973
54 N800e482b26384eac98e6fc95629c26e4 rdf:first sg:person.011542074410.00
55 rdf:rest N28291d6f2d634e279bcc0ff46b5bcbd0
56 N970d3956024348d8952de358e569314c schema:name dimensions_id
57 schema:value pub.1025103491
58 rdf:type schema:PropertyValue
59 Nb8fc313111d2470daa3faab756b75624 schema:familyName Rozenberg
60 schema:givenName Grzegorz
61 rdf:type schema:Person
62 Nd1abea258d374e3ca8996a4d75126df8 schema:name Springer Nature - SN SciGraph project
63 rdf:type schema:Organization
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)


...