A characterization of context-free NCE graph languages by monadic second-order logic on trees View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1991

AUTHORS

Joost Engelfriet

ABSTRACT

A graph language L is in the class C-edNCE of context-free NCE graph languages if and only if L=f(T) where f is a function on graphs that can be defined in monadic second-order logic and T is the set of all trees over some ranked alphabet. This logical characterization implies a large number of closure and decidability properties of the class C-edNCE. More... »

PAGES

311-327

References to SciGraph publications

Book

TITLE

Graph Grammars and Their Application to Computer Science

ISBN

3-540-54478-X

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bfb0017397

DOI

http://dx.doi.org/10.1007/bfb0017397

DIMENSIONS

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


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": [
      {
        "affiliation": {
          "alternateName": "Leiden University", 
          "id": "https://www.grid.ac/institutes/grid.5132.5", 
          "name": [
            "Dept. of Computer Science, Leiden University, P. O. Box 9512, 2300 RA\u00a0Leiden, 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"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0166-218x(81)90013-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012596998"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01692060", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013326091", 
          "https://doi.org/10.1007/bf01692060"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01692060", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013326091", 
          "https://doi.org/10.1007/bf01692060"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01692060", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013326091", 
          "https://doi.org/10.1007/bf01692060"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0166-218x(87)90054-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026811891"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0166-218x(87)90054-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026811891"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0890-5401(90)90043-h", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027180474"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00288976", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033100693", 
          "https://doi.org/10.1007/bf00288976"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00288976", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033100693", 
          "https://doi.org/10.1007/bf00288976"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0890-5401(90)90038-j", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033751887"
        ], 
        "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.1016/0304-3975(87)90102-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038921884"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0019-9958(86)80045-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039025420"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0022-0000(90)90002-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046567925"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0890-5401(89)90030-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049234436"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1991", 
    "datePublishedReg": "1991-01-01", 
    "description": "A graph language L is in the class C-edNCE of context-free NCE graph languages if and only if L=f(T) where f is a function on graphs that can be defined in monadic second-order logic and T is the set of all trees over some ranked alphabet. This logical characterization implies a large number of closure and decidability properties of the class C-edNCE.", 
    "editor": [
      {
        "familyName": "Ehrig", 
        "givenName": "Hartmut", 
        "type": "Person"
      }, 
      {
        "familyName": "Kreowski", 
        "givenName": "Hans-J\u00f6rg", 
        "type": "Person"
      }, 
      {
        "familyName": "Rozenberg", 
        "givenName": "Grzegorz", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/bfb0017397", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "3-540-54478-X"
      ], 
      "name": "Graph Grammars and Their Application to Computer Science", 
      "type": "Book"
    }, 
    "name": "A characterization of context-free NCE graph languages by monadic second-order logic on trees", 
    "pagination": "311-327", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bfb0017397"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "9d4f97dbee25faf473b5bc762ea47da47c503b2fc0e08bad78aa45502b929f3a"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1033021795"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin/Heidelberg", 
      "name": "Springer-Verlag", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/bfb0017397", 
      "https://app.dimensions.ai/details/publication/pub.1033021795"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T15:22", 
    "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_00000263.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/BFb0017397"
  }
]
 

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/bfb0017397'

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/bfb0017397'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bfb0017397'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bfb0017397'


 

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

110 TRIPLES      23 PREDICATES      38 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bfb0017397 schema:about anzsrc-for:20
2 anzsrc-for:2004
3 schema:author N6c3a6107c8a4442bb0f765efaf19d020
4 schema:citation sg:pub.10.1007/bf00288976
5 sg:pub.10.1007/bf01691346
6 sg:pub.10.1007/bf01692060
7 https://doi.org/10.1016/0022-0000(90)90002-3
8 https://doi.org/10.1016/0166-218x(81)90013-5
9 https://doi.org/10.1016/0166-218x(87)90054-0
10 https://doi.org/10.1016/0304-3975(87)90102-2
11 https://doi.org/10.1016/0890-5401(89)90030-8
12 https://doi.org/10.1016/0890-5401(90)90038-j
13 https://doi.org/10.1016/0890-5401(90)90043-h
14 https://doi.org/10.1016/s0019-9958(86)80045-6
15 schema:datePublished 1991
16 schema:datePublishedReg 1991-01-01
17 schema:description A graph language L is in the class C-edNCE of context-free NCE graph languages if and only if L=f(T) where f is a function on graphs that can be defined in monadic second-order logic and T is the set of all trees over some ranked alphabet. This logical characterization implies a large number of closure and decidability properties of the class C-edNCE.
18 schema:editor N4ef6e0e25e2b4be3a2182ede7645a7f1
19 schema:genre chapter
20 schema:inLanguage en
21 schema:isAccessibleForFree false
22 schema:isPartOf N5f52b34ca9c5422c9740bc05dadf24bd
23 schema:name A characterization of context-free NCE graph languages by monadic second-order logic on trees
24 schema:pagination 311-327
25 schema:productId N7170f93d5a0843f8a32597b70b463386
26 N95516dc1f17a4e4ab9a1977d5e450682
27 Nef5aec8bf6f64a03b24100de2c1047c9
28 schema:publisher N2605196061ae4c21b5ec826c2923cd60
29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033021795
30 https://doi.org/10.1007/bfb0017397
31 schema:sdDatePublished 2019-04-15T15:22
32 schema:sdLicense https://scigraph.springernature.com/explorer/license/
33 schema:sdPublisher Nf53cd340dbad45b49e6048ad8ca12ce6
34 schema:url http://link.springer.com/10.1007/BFb0017397
35 sgo:license sg:explorer/license/
36 sgo:sdDataset chapters
37 rdf:type schema:Chapter
38 N16e572d29b984b699c0d1d11215a4b02 rdf:first N47b2a59d52464ee0992322d064b6b6c9
39 rdf:rest N2efd007ff2a045dd83a72fde0dede9e5
40 N2605196061ae4c21b5ec826c2923cd60 schema:location Berlin/Heidelberg
41 schema:name Springer-Verlag
42 rdf:type schema:Organisation
43 N2efd007ff2a045dd83a72fde0dede9e5 rdf:first N49535572b0924a4fa79cfd953e8f7ac9
44 rdf:rest rdf:nil
45 N47b2a59d52464ee0992322d064b6b6c9 schema:familyName Kreowski
46 schema:givenName Hans-Jörg
47 rdf:type schema:Person
48 N49535572b0924a4fa79cfd953e8f7ac9 schema:familyName Rozenberg
49 schema:givenName Grzegorz
50 rdf:type schema:Person
51 N4ef6e0e25e2b4be3a2182ede7645a7f1 rdf:first N77d1d14e50904ae3a986980b9ac39295
52 rdf:rest N16e572d29b984b699c0d1d11215a4b02
53 N5f52b34ca9c5422c9740bc05dadf24bd schema:isbn 3-540-54478-X
54 schema:name Graph Grammars and Their Application to Computer Science
55 rdf:type schema:Book
56 N6c3a6107c8a4442bb0f765efaf19d020 rdf:first sg:person.014574236321.39
57 rdf:rest rdf:nil
58 N7170f93d5a0843f8a32597b70b463386 schema:name dimensions_id
59 schema:value pub.1033021795
60 rdf:type schema:PropertyValue
61 N77d1d14e50904ae3a986980b9ac39295 schema:familyName Ehrig
62 schema:givenName Hartmut
63 rdf:type schema:Person
64 N95516dc1f17a4e4ab9a1977d5e450682 schema:name doi
65 schema:value 10.1007/bfb0017397
66 rdf:type schema:PropertyValue
67 Nef5aec8bf6f64a03b24100de2c1047c9 schema:name readcube_id
68 schema:value 9d4f97dbee25faf473b5bc762ea47da47c503b2fc0e08bad78aa45502b929f3a
69 rdf:type schema:PropertyValue
70 Nf53cd340dbad45b49e6048ad8ca12ce6 schema:name Springer Nature - SN SciGraph project
71 rdf:type schema:Organization
72 anzsrc-for:20 schema:inDefinedTermSet anzsrc-for:
73 schema:name Language, Communication and Culture
74 rdf:type schema:DefinedTerm
75 anzsrc-for:2004 schema:inDefinedTermSet anzsrc-for:
76 schema:name Linguistics
77 rdf:type schema:DefinedTerm
78 sg:person.014574236321.39 schema:affiliation https://www.grid.ac/institutes/grid.5132.5
79 schema:familyName Engelfriet
80 schema:givenName Joost
81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014574236321.39
82 rdf:type schema:Person
83 sg:pub.10.1007/bf00288976 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033100693
84 https://doi.org/10.1007/bf00288976
85 rdf:type schema:CreativeWork
86 sg:pub.10.1007/bf01691346 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038809008
87 https://doi.org/10.1007/bf01691346
88 rdf:type schema:CreativeWork
89 sg:pub.10.1007/bf01692060 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013326091
90 https://doi.org/10.1007/bf01692060
91 rdf:type schema:CreativeWork
92 https://doi.org/10.1016/0022-0000(90)90002-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046567925
93 rdf:type schema:CreativeWork
94 https://doi.org/10.1016/0166-218x(81)90013-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012596998
95 rdf:type schema:CreativeWork
96 https://doi.org/10.1016/0166-218x(87)90054-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026811891
97 rdf:type schema:CreativeWork
98 https://doi.org/10.1016/0304-3975(87)90102-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038921884
99 rdf:type schema:CreativeWork
100 https://doi.org/10.1016/0890-5401(89)90030-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049234436
101 rdf:type schema:CreativeWork
102 https://doi.org/10.1016/0890-5401(90)90038-j schema:sameAs https://app.dimensions.ai/details/publication/pub.1033751887
103 rdf:type schema:CreativeWork
104 https://doi.org/10.1016/0890-5401(90)90043-h schema:sameAs https://app.dimensions.ai/details/publication/pub.1027180474
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1016/s0019-9958(86)80045-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039025420
107 rdf:type schema:CreativeWork
108 https://www.grid.ac/institutes/grid.5132.5 schema:alternateName Leiden University
109 schema:name Dept. of Computer Science, Leiden University, P. O. Box 9512, 2300 RA Leiden, The Netherlands
110 rdf:type schema:Organization
 




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


...