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

  • 2003-08. A comparison of pebble tree transducers with macro tree transducers in ACTA INFORMATICA
  • 2003. The Macro Tree Transducer Hierarchy Collapses for Functions of Linear Size Increase in FST TCS 2003: FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE
  • 1998. Syntax-Directed Semantics, Formal Models Based on Tree Transducers in NONE
  • 1997. Context-Free Graph Grammars in HANDBOOK OF FORMAL LANGUAGES
  • 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 N4740f493ad5a4da4a1474e3659c7699d
    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 Nd70bd1193c93400ba81e1f561f129c7e
    30 schema:genre chapter
    31 schema:inLanguage en
    32 schema:isAccessibleForFree true
    33 schema:isPartOf Need702c3203748be96cded87e94e9305
    34 schema:name The Equivalence Problem for Deterministic MSO Tree Transducers Is Decidable
    35 schema:pagination 495-504
    36 schema:productId N0f64d2952b054c968e1f56cd0539d6ca
    37 N10b730482dff42489905b35c6714a711
    38 N82d18e6897304e7483a323c6a3e0ec8e
    39 schema:publisher Na8e82105def34f31a23a7776a17e9a58
    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 Nb993ae7a84cf4af59af0a20d62731f59
    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 N05720feed5fc44f0880881734fa5bd82 schema:familyName Sarukkai
    50 schema:givenName Sundar
    51 rdf:type schema:Person
    52 N07b2ad9a178545319373db1237e5b740 rdf:first sg:person.016240662443.33
    53 rdf:rest rdf:nil
    54 N0f64d2952b054c968e1f56cd0539d6ca schema:name readcube_id
    55 schema:value 1f11fe880d7c436c0eac5994f97dfbb578fb934616a0c27e57c5424c9a62799e
    56 rdf:type schema:PropertyValue
    57 N10b730482dff42489905b35c6714a711 schema:name dimensions_id
    58 schema:value pub.1006522937
    59 rdf:type schema:PropertyValue
    60 N3b37b1ea47bb482284fe1abcfe67a5fd schema:familyName Sen
    61 schema:givenName Sandeep
    62 rdf:type schema:Person
    63 N4740f493ad5a4da4a1474e3659c7699d rdf:first sg:person.014574236321.39
    64 rdf:rest N07b2ad9a178545319373db1237e5b740
    65 N82d18e6897304e7483a323c6a3e0ec8e schema:name doi
    66 schema:value 10.1007/11590156_40
    67 rdf:type schema:PropertyValue
    68 Na8e82105def34f31a23a7776a17e9a58 schema:location Berlin, Heidelberg
    69 schema:name Springer Berlin Heidelberg
    70 rdf:type schema:Organisation
    71 Nb993ae7a84cf4af59af0a20d62731f59 schema:name Springer Nature - SN SciGraph project
    72 rdf:type schema:Organization
    73 Nd70bd1193c93400ba81e1f561f129c7e rdf:first N05720feed5fc44f0880881734fa5bd82
    74 rdf:rest Ne96fa375a552422b9ed568abfdb0c78b
    75 Ne96fa375a552422b9ed568abfdb0c78b rdf:first N3b37b1ea47bb482284fe1abcfe67a5fd
    76 rdf:rest rdf:nil
    77 Need702c3203748be96cded87e94e9305 schema:isbn 978-3-540-30495-1
    78 978-3-540-32419-5
    79 schema:name FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
    80 rdf:type schema:Book
    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)


    ...