The Equivalence Problem for Deterministic MSO Tree Transducers Is Decidable View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2005

AUTHORS

Joost Engelfriet , Sebastian Maneth

ABSTRACT

It is decidable for deterministic MSO definable graph-to-string or graph-to-tree transducers whether they are equivalent on a context-free set of graphs.

PAGES

495-504

References to SciGraph publications

Book

TITLE

FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science

ISBN

978-3-540-30495-1
978-3-540-32419-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11590156_40

DOI

http://dx.doi.org/10.1007/11590156_40

DIMENSIONS

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


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", 
    "author": [
      {
        "affiliation": {
          "alternateName": "Leiden University", 
          "id": "https://www.grid.ac/institutes/grid.5132.5", 
          "name": [
            "LIACS, Leiden University, 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"
      }, 
      {
        "affiliation": {
          "alternateName": "\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne", 
          "id": "https://www.grid.ac/institutes/grid.5333.6", 
          "name": [
            "Facult\u00e9 I & C, EPFL, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Maneth", 
        "givenName": "Sebastian", 
        "id": "sg:person.016240662443.33", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016240662443.33"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/978-3-642-59126-6_3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007075929", 
          "https://doi.org/10.1007/978-3-642-59126-6_3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-59126-6_3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007075929", 
          "https://doi.org/10.1007/978-3-642-59126-6_3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0304-3975(94)90268-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007706893"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0304-3975(82)90061-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008165138"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-24597-1_28", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010155209", 
          "https://doi.org/10.1007/978-3-540-24597-1_28"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-24597-1_28", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010155209", 
          "https://doi.org/10.1007/978-3-540-24597-1_28"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/inco.1999.2807", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010394805"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1013725897", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-72248-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013725897", 
          "https://doi.org/10.1007/978-3-642-72248-6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-72248-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013725897", 
          "https://doi.org/10.1007/978-3-642-72248-6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/321466.321473", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015653122"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00236-003-0120-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017699949", 
          "https://doi.org/10.1007/s00236-003-0120-0"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/s0002-9947-1964-0181500-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022390766"
        ], 
        "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.1145/1065167.1065203", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032583410"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/b978-0-12-115350-2.50014-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034871415"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/321356.321364", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036285496"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/jcss.1999.1684", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038794477"
        ], 
        "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.1016/s0019-9958(82)90786-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047236816"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/371316.371512", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052213520"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0022-0000(02)00030-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052657880"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0211035", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841651"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0216018", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841964"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0097539701394511", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062879323"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.2307/1994067", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1069689012"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/9789812384720_0005", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1088707211"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2005", 
    "datePublishedReg": "2005-01-01", 
    "description": "It is decidable for deterministic MSO definable graph-to-string or graph-to-tree transducers whether they are equivalent on a context-free set of graphs.", 
    "editor": [
      {
        "familyName": "Sarukkai", 
        "givenName": "Sundar", 
        "type": "Person"
      }, 
      {
        "familyName": "Sen", 
        "givenName": "Sandeep", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11590156_40", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-30495-1", 
        "978-3-540-32419-5"
      ], 
      "name": "FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science", 
      "type": "Book"
    }, 
    "name": "The Equivalence Problem for Deterministic MSO Tree Transducers Is Decidable", 
    "pagination": "495-504", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1006522937"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11590156_40"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "1f11fe880d7c436c0eac5994f97dfbb578fb934616a0c27e57c5424c9a62799e"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11590156_40", 
      "https://app.dimensions.ai/details/publication/pub.1006522937"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T08:27", 
    "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/0000000363_0000000363/records_70061_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F11590156_40"
  }
]
 

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/11590156_40'

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/11590156_40'

Turtle is a human-readable linked data format.

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

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

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


 

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

147 TRIPLES      22 PREDICATES      49 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11590156_40 schema:author Nb3268f1b633a4a1484de4eda8f9555d3
2 schema:citation sg:pub.10.1007/978-3-540-24597-1_28
3 sg:pub.10.1007/978-3-642-59126-6_3
4 sg:pub.10.1007/978-3-642-72248-6
5 sg:pub.10.1007/s00236-003-0120-0
6 https://app.dimensions.ai/details/publication/pub.1013725897
7 https://doi.org/10.1006/inco.1999.2807
8 https://doi.org/10.1006/jcss.1999.1684
9 https://doi.org/10.1016/0022-0000(80)90058-6
10 https://doi.org/10.1016/0304-3975(82)90061-5
11 https://doi.org/10.1016/0304-3975(94)90268-2
12 https://doi.org/10.1016/b978-0-12-115350-2.50014-2
13 https://doi.org/10.1016/s0019-9958(71)90706-6
14 https://doi.org/10.1016/s0019-9958(82)90786-0
15 https://doi.org/10.1016/s0022-0000(02)00030-2
16 https://doi.org/10.1090/s0002-9947-1964-0181500-1
17 https://doi.org/10.1137/0211035
18 https://doi.org/10.1137/0216018
19 https://doi.org/10.1137/s0097539701394511
20 https://doi.org/10.1142/9789812384720_0005
21 https://doi.org/10.1145/1065167.1065203
22 https://doi.org/10.1145/321356.321364
23 https://doi.org/10.1145/321466.321473
24 https://doi.org/10.1145/371316.371512
25 https://doi.org/10.2307/1994067
26 schema:datePublished 2005
27 schema:datePublishedReg 2005-01-01
28 schema:description It is decidable for deterministic MSO definable graph-to-string or graph-to-tree transducers whether they are equivalent on a context-free set of graphs.
29 schema:editor Nee8282adb30f4dab918508cc5c851948
30 schema:genre chapter
31 schema:inLanguage en
32 schema:isAccessibleForFree true
33 schema:isPartOf N6e6065c40aec48ceb1b38a203603947f
34 schema:name The Equivalence Problem for Deterministic MSO Tree Transducers Is Decidable
35 schema:pagination 495-504
36 schema:productId N3802a3993e1f4e8ea7e268f9f8d3bace
37 N5a93eef2fbef4373ac0c8ac81ba5242a
38 Na18f71b3351c40af977c9298df50027a
39 schema:publisher N13eff8c2019049fca64562f8b7926c87
40 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006522937
41 https://doi.org/10.1007/11590156_40
42 schema:sdDatePublished 2019-04-16T08:27
43 schema:sdLicense https://scigraph.springernature.com/explorer/license/
44 schema:sdPublisher Ndbce8405f90448f886eabc0c88c951a2
45 schema:url https://link.springer.com/10.1007%2F11590156_40
46 sgo:license sg:explorer/license/
47 sgo:sdDataset chapters
48 rdf:type schema:Chapter
49 N039229c6d3e34650baa04b42821a2bd5 rdf:first sg:person.016240662443.33
50 rdf:rest rdf:nil
51 N13eff8c2019049fca64562f8b7926c87 schema:location Berlin, Heidelberg
52 schema:name Springer Berlin Heidelberg
53 rdf:type schema:Organisation
54 N3802a3993e1f4e8ea7e268f9f8d3bace schema:name doi
55 schema:value 10.1007/11590156_40
56 rdf:type schema:PropertyValue
57 N5a93eef2fbef4373ac0c8ac81ba5242a schema:name readcube_id
58 schema:value 1f11fe880d7c436c0eac5994f97dfbb578fb934616a0c27e57c5424c9a62799e
59 rdf:type schema:PropertyValue
60 N6e6065c40aec48ceb1b38a203603947f schema:isbn 978-3-540-30495-1
61 978-3-540-32419-5
62 schema:name FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
63 rdf:type schema:Book
64 Na18f71b3351c40af977c9298df50027a schema:name dimensions_id
65 schema:value pub.1006522937
66 rdf:type schema:PropertyValue
67 Na95940e9c8434715aef901321866c13a schema:familyName Sarukkai
68 schema:givenName Sundar
69 rdf:type schema:Person
70 Nad7c7f27f0d64192a7cacfb73a52417e schema:familyName Sen
71 schema:givenName Sandeep
72 rdf:type schema:Person
73 Nb3268f1b633a4a1484de4eda8f9555d3 rdf:first sg:person.014574236321.39
74 rdf:rest N039229c6d3e34650baa04b42821a2bd5
75 Nc468357da0c74ef58ff1a0f8cb7222ad rdf:first Nad7c7f27f0d64192a7cacfb73a52417e
76 rdf:rest rdf:nil
77 Ndbce8405f90448f886eabc0c88c951a2 schema:name Springer Nature - SN SciGraph project
78 rdf:type schema:Organization
79 Nee8282adb30f4dab918508cc5c851948 rdf:first Na95940e9c8434715aef901321866c13a
80 rdf:rest Nc468357da0c74ef58ff1a0f8cb7222ad
81 sg:person.014574236321.39 schema:affiliation https://www.grid.ac/institutes/grid.5132.5
82 schema:familyName Engelfriet
83 schema:givenName Joost
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014574236321.39
85 rdf:type schema:Person
86 sg:person.016240662443.33 schema:affiliation https://www.grid.ac/institutes/grid.5333.6
87 schema:familyName Maneth
88 schema:givenName Sebastian
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016240662443.33
90 rdf:type schema:Person
91 sg:pub.10.1007/978-3-540-24597-1_28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010155209
92 https://doi.org/10.1007/978-3-540-24597-1_28
93 rdf:type schema:CreativeWork
94 sg:pub.10.1007/978-3-642-59126-6_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007075929
95 https://doi.org/10.1007/978-3-642-59126-6_3
96 rdf:type schema:CreativeWork
97 sg:pub.10.1007/978-3-642-72248-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013725897
98 https://doi.org/10.1007/978-3-642-72248-6
99 rdf:type schema:CreativeWork
100 sg:pub.10.1007/s00236-003-0120-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017699949
101 https://doi.org/10.1007/s00236-003-0120-0
102 rdf:type schema:CreativeWork
103 https://app.dimensions.ai/details/publication/pub.1013725897 schema:CreativeWork
104 https://doi.org/10.1006/inco.1999.2807 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010394805
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1006/jcss.1999.1684 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038794477
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1016/0022-0000(80)90058-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028307536
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1016/0304-3975(82)90061-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008165138
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1016/0304-3975(94)90268-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007706893
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1016/b978-0-12-115350-2.50014-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034871415
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1016/s0019-9958(71)90706-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046403722
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1016/s0019-9958(82)90786-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047236816
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1016/s0022-0000(02)00030-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052657880
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1090/s0002-9947-1964-0181500-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022390766
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1137/0211035 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841651
125 rdf:type schema:CreativeWork
126 https://doi.org/10.1137/0216018 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841964
127 rdf:type schema:CreativeWork
128 https://doi.org/10.1137/s0097539701394511 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879323
129 rdf:type schema:CreativeWork
130 https://doi.org/10.1142/9789812384720_0005 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088707211
131 rdf:type schema:CreativeWork
132 https://doi.org/10.1145/1065167.1065203 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032583410
133 rdf:type schema:CreativeWork
134 https://doi.org/10.1145/321356.321364 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036285496
135 rdf:type schema:CreativeWork
136 https://doi.org/10.1145/321466.321473 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015653122
137 rdf:type schema:CreativeWork
138 https://doi.org/10.1145/371316.371512 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052213520
139 rdf:type schema:CreativeWork
140 https://doi.org/10.2307/1994067 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069689012
141 rdf:type schema:CreativeWork
142 https://www.grid.ac/institutes/grid.5132.5 schema:alternateName Leiden University
143 schema:name LIACS, Leiden University, The Netherlands
144 rdf:type schema:Organization
145 https://www.grid.ac/institutes/grid.5333.6 schema:alternateName École Polytechnique Fédérale de Lausanne
146 schema:name Faculté I & C, EPFL, Switzerland
147 rdf:type schema:Organization
 




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


...