Forward and backward application of symbolic tree transducers View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2014-03-21

AUTHORS

Zoltán Fülöp, Heiko Vogler

ABSTRACT

We consider symbolic tree automata (sta) and symbolic regular tree grammars and their corresponding classes of tree languages: s-recognizable tree languages and s-regular tree languages. We prove that the following three classes are equal: the class of s-recognizable tree languages, the class of s-regular tree languages, and the class of images of classical recognizable tree languages under tree relabelings. Moreover, the sta and the recently introduced variable tree automata are incomparable with respect to their recognition power. Also, we consider symbolic tree transducers (stt) and prove the following theorems. The syntactic composition of two stt computes the composition of the tree transformations computed by each stt, provided that (1) the first one is deterministic or the second one is linear and (2) the first one is total or the second one is nondeleting. Backward application of an stt to any s-recognizable tree language yields an s-recognizable tree language. There is a linear stt of which the range is not an s-recognizable tree language. Forward application of simple and linear stt preserves s-recognizability. A restricted version of both the type checking problem of simple and linear stt, and the inverse type checking problem of arbitrary stt is decidable. Since we deal with trees over infinite alphabets, we require appropriate conditions on sta and stt such that all the proofs are constructive. More... »

PAGES

297-325

References to SciGraph publications

  • 2010. Variable Automata over Infinite Alphabets in LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS
  • 1975-06. Bottom-up and top-down tree transformations— a comparison in THEORY OF COMPUTING SYSTEMS
  • 2007-01-01. Rewriting Systems with Data in FUNDAMENTALS OF COMPUTATION THEORY
  • <error retrieving object. in <ERROR RETRIEVING OBJECT
  • 2012. Symbolic Tree Transducers in PERSPECTIVES OF SYSTEMS INFORMATICS
  • 1998. Syntax-Directed Semantics, Formal Models Based on Tree Transducers in NONE
  • 1997. Tree Languages in HANDBOOK OF FORMAL LANGUAGES
  • 2008-01-01. Tree Automata over Infinite Alphabets in PILLARS OF COMPUTER SCIENCE
  • 2011. Variable Tree Automata over Infinite Ranked Alphabets in ALGEBRAIC INFORMATICS
  • 2003-08. A comparison of pebble tree transducers with macro tree transducers in ACTA INFORMATICA
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00236-014-0197-7

    DOI

    http://dx.doi.org/10.1007/s00236-014-0197-7

    DIMENSIONS

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


    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/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0803", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computer Software", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0804", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Data Format", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Department of Foundations of Computer Science, University of Szeged, \u00c1rp\u00e1d t\u00e9r 2, 6720, Szeged, Hungary", 
              "id": "http://www.grid.ac/institutes/grid.9008.1", 
              "name": [
                "Department of Foundations of Computer Science, University of Szeged, \u00c1rp\u00e1d t\u00e9r 2, 6720, Szeged, Hungary"
              ], 
              "type": "Organization"
            }, 
            "familyName": "F\u00fcl\u00f6p", 
            "givenName": "Zolt\u00e1n", 
            "id": "sg:person.014007607055.43", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014007607055.43"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Faculty of Computer Science, Technische Universit\u00e4t Dresden, Mommsenstr.\u00a013, 01062, Dresden, Germany", 
              "id": "http://www.grid.ac/institutes/grid.4488.0", 
              "name": [
                "Faculty of Computer Science, Technische Universit\u00e4t Dresden, Mommsenstr.\u00a013, 01062, Dresden, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Vogler", 
            "givenName": "Heiko", 
            "id": "sg:person.014562633673.93", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014562633673.93"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf01704020", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006876172", 
              "https://doi.org/10.1007/bf01704020"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-59126-6_1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000867424", 
              "https://doi.org/10.1007/978-3-642-59126-6_1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-13089-2_47", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029571936", 
              "https://doi.org/10.1007/978-3-642-13089-2_47"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-21493-6_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001500956", 
              "https://doi.org/10.1007/978-3-642-21493-6_16"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-74240-1_1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031882057", 
              "https://doi.org/10.1007/978-3-540-74240-1_1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01695769", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033919759", 
              "https://doi.org/10.1007/bf01695769"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-29709-0_32", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040264786", 
              "https://doi.org/10.1007/978-3-642-29709-0_32"
            ], 
            "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-540-78127-1_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019954175", 
              "https://doi.org/10.1007/978-3-540-78127-1_21"
            ], 
            "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"
          }
        ], 
        "datePublished": "2014-03-21", 
        "datePublishedReg": "2014-03-21", 
        "description": "We consider symbolic tree automata (sta) and symbolic regular tree grammars and their corresponding classes of tree languages: s-recognizable tree languages and s-regular tree languages. We prove that the following three classes are equal: the class of s-recognizable tree languages, the class of s-regular tree languages, and the class of images of classical recognizable tree languages under tree relabelings. Moreover, the sta and the recently introduced variable tree automata are incomparable with respect to their recognition power. Also, we consider symbolic tree transducers (stt) and prove the following theorems. The syntactic composition of two stt computes the composition of the tree transformations computed by each stt, provided that (1) the first one is deterministic or the second one is linear and (2) the first one is total or the second one is nondeleting. Backward application of an stt to any s-recognizable tree language yields an s-recognizable tree language. There is a linear stt of which the range is not an s-recognizable tree language. Forward application of simple and linear stt preserves s-recognizability. A restricted version of both the type checking problem of simple and linear stt, and the inverse type checking problem of arbitrary stt is decidable. Since we deal with trees over infinite alphabets, we require appropriate conditions on sta and stt such that all the proofs are constructive.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00236-014-0197-7", 
        "inLanguage": "en", 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1133515", 
            "issn": [
              "0001-5903", 
              "1432-0525"
            ], 
            "name": "Acta Informatica", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "5", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "51"
          }
        ], 
        "keywords": [
          "recognizable tree languages", 
          "regular tree languages", 
          "tree languages", 
          "backward application", 
          "tree transducers", 
          "language", 
          "syntactic composition", 
          "tree automata", 
          "recognition power", 
          "regular tree grammars", 
          "tree transformations", 
          "infinite alphabets", 
          "inverse type", 
          "grammar", 
          "alphabet", 
          "tree grammars", 
          "recognizability", 
          "corresponding class", 
          "automata", 
          "class", 
          "restricted version", 
          "version", 
          "second one", 
          "one", 
          "power", 
          "images", 
          "transformation", 
          "class of images", 
          "STT", 
          "relabeling", 
          "types", 
          "problem", 
          "respect", 
          "range", 
          "proof", 
          "composition", 
          "applications", 
          "STA", 
          "trees", 
          "conditions", 
          "compute", 
          "appropriate conditions", 
          "theorem", 
          "transducer"
        ], 
        "name": "Forward and backward application of symbolic tree transducers", 
        "pagination": "297-325", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1044653584"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00236-014-0197-7"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00236-014-0197-7", 
          "https://app.dimensions.ai/details/publication/pub.1044653584"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-05-20T07:28", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/article/article_614.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00236-014-0197-7"
      }
    ]
     

    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/s00236-014-0197-7'

    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/s00236-014-0197-7'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00236-014-0197-7'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00236-014-0197-7'


     

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

    160 TRIPLES      22 PREDICATES      81 URIs      61 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00236-014-0197-7 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 anzsrc-for:0803
    4 anzsrc-for:0804
    5 schema:author Nd24992787e98462da754ae132728e24b
    6 schema:citation sg:pub.10.1007/978-3-540-74240-1_1
    7 sg:pub.10.1007/978-3-540-78127-1_21
    8 sg:pub.10.1007/978-3-642-13089-2_47
    9 sg:pub.10.1007/978-3-642-21493-6_16
    10 sg:pub.10.1007/978-3-642-29709-0_32
    11 sg:pub.10.1007/978-3-642-59126-6_1
    12 sg:pub.10.1007/978-3-642-72248-6
    13 sg:pub.10.1007/bf01695769
    14 sg:pub.10.1007/bf01704020
    15 sg:pub.10.1007/s00236-003-0120-0
    16 schema:datePublished 2014-03-21
    17 schema:datePublishedReg 2014-03-21
    18 schema:description We consider symbolic tree automata (sta) and symbolic regular tree grammars and their corresponding classes of tree languages: s-recognizable tree languages and s-regular tree languages. We prove that the following three classes are equal: the class of s-recognizable tree languages, the class of s-regular tree languages, and the class of images of classical recognizable tree languages under tree relabelings. Moreover, the sta and the recently introduced variable tree automata are incomparable with respect to their recognition power. Also, we consider symbolic tree transducers (stt) and prove the following theorems. The syntactic composition of two stt computes the composition of the tree transformations computed by each stt, provided that (1) the first one is deterministic or the second one is linear and (2) the first one is total or the second one is nondeleting. Backward application of an stt to any s-recognizable tree language yields an s-recognizable tree language. There is a linear stt of which the range is not an s-recognizable tree language. Forward application of simple and linear stt preserves s-recognizability. A restricted version of both the type checking problem of simple and linear stt, and the inverse type checking problem of arbitrary stt is decidable. Since we deal with trees over infinite alphabets, we require appropriate conditions on sta and stt such that all the proofs are constructive.
    19 schema:genre article
    20 schema:inLanguage en
    21 schema:isAccessibleForFree true
    22 schema:isPartOf N07fe07f499e347339145575e29a0aced
    23 Nee393fadfd204043afbff24dfdb136f5
    24 sg:journal.1133515
    25 schema:keywords STA
    26 STT
    27 alphabet
    28 applications
    29 appropriate conditions
    30 automata
    31 backward application
    32 class
    33 class of images
    34 composition
    35 compute
    36 conditions
    37 corresponding class
    38 grammar
    39 images
    40 infinite alphabets
    41 inverse type
    42 language
    43 one
    44 power
    45 problem
    46 proof
    47 range
    48 recognition power
    49 recognizability
    50 recognizable tree languages
    51 regular tree grammars
    52 regular tree languages
    53 relabeling
    54 respect
    55 restricted version
    56 second one
    57 syntactic composition
    58 theorem
    59 transducer
    60 transformation
    61 tree automata
    62 tree grammars
    63 tree languages
    64 tree transducers
    65 tree transformations
    66 trees
    67 types
    68 version
    69 schema:name Forward and backward application of symbolic tree transducers
    70 schema:pagination 297-325
    71 schema:productId N0b4ad3e4a5dd4a2eb453b42ebaadb24f
    72 N9bb9487313a740a7b437bf65ae906d11
    73 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044653584
    74 https://doi.org/10.1007/s00236-014-0197-7
    75 schema:sdDatePublished 2022-05-20T07:28
    76 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    77 schema:sdPublisher Nb62e7ff7e92248e0aa0cddcc9a5d3ee8
    78 schema:url https://doi.org/10.1007/s00236-014-0197-7
    79 sgo:license sg:explorer/license/
    80 sgo:sdDataset articles
    81 rdf:type schema:ScholarlyArticle
    82 N07fe07f499e347339145575e29a0aced schema:volumeNumber 51
    83 rdf:type schema:PublicationVolume
    84 N0b4ad3e4a5dd4a2eb453b42ebaadb24f schema:name dimensions_id
    85 schema:value pub.1044653584
    86 rdf:type schema:PropertyValue
    87 N381642a1d9dd4b81aea39b8e76248234 rdf:first sg:person.014562633673.93
    88 rdf:rest rdf:nil
    89 N9bb9487313a740a7b437bf65ae906d11 schema:name doi
    90 schema:value 10.1007/s00236-014-0197-7
    91 rdf:type schema:PropertyValue
    92 Nb62e7ff7e92248e0aa0cddcc9a5d3ee8 schema:name Springer Nature - SN SciGraph project
    93 rdf:type schema:Organization
    94 Nd24992787e98462da754ae132728e24b rdf:first sg:person.014007607055.43
    95 rdf:rest N381642a1d9dd4b81aea39b8e76248234
    96 Nee393fadfd204043afbff24dfdb136f5 schema:issueNumber 5
    97 rdf:type schema:PublicationIssue
    98 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    99 schema:name Information and Computing Sciences
    100 rdf:type schema:DefinedTerm
    101 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    102 schema:name Computation Theory and Mathematics
    103 rdf:type schema:DefinedTerm
    104 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
    105 schema:name Computer Software
    106 rdf:type schema:DefinedTerm
    107 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
    108 schema:name Data Format
    109 rdf:type schema:DefinedTerm
    110 sg:journal.1133515 schema:issn 0001-5903
    111 1432-0525
    112 schema:name Acta Informatica
    113 schema:publisher Springer Nature
    114 rdf:type schema:Periodical
    115 sg:person.014007607055.43 schema:affiliation grid-institutes:grid.9008.1
    116 schema:familyName Fülöp
    117 schema:givenName Zoltán
    118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014007607055.43
    119 rdf:type schema:Person
    120 sg:person.014562633673.93 schema:affiliation grid-institutes:grid.4488.0
    121 schema:familyName Vogler
    122 schema:givenName Heiko
    123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014562633673.93
    124 rdf:type schema:Person
    125 sg:pub.10.1007/978-3-540-74240-1_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031882057
    126 https://doi.org/10.1007/978-3-540-74240-1_1
    127 rdf:type schema:CreativeWork
    128 sg:pub.10.1007/978-3-540-78127-1_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019954175
    129 https://doi.org/10.1007/978-3-540-78127-1_21
    130 rdf:type schema:CreativeWork
    131 sg:pub.10.1007/978-3-642-13089-2_47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029571936
    132 https://doi.org/10.1007/978-3-642-13089-2_47
    133 rdf:type schema:CreativeWork
    134 sg:pub.10.1007/978-3-642-21493-6_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001500956
    135 https://doi.org/10.1007/978-3-642-21493-6_16
    136 rdf:type schema:CreativeWork
    137 sg:pub.10.1007/978-3-642-29709-0_32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040264786
    138 https://doi.org/10.1007/978-3-642-29709-0_32
    139 rdf:type schema:CreativeWork
    140 sg:pub.10.1007/978-3-642-59126-6_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000867424
    141 https://doi.org/10.1007/978-3-642-59126-6_1
    142 rdf:type schema:CreativeWork
    143 sg:pub.10.1007/978-3-642-72248-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013725897
    144 https://doi.org/10.1007/978-3-642-72248-6
    145 rdf:type schema:CreativeWork
    146 sg:pub.10.1007/bf01695769 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033919759
    147 https://doi.org/10.1007/bf01695769
    148 rdf:type schema:CreativeWork
    149 sg:pub.10.1007/bf01704020 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006876172
    150 https://doi.org/10.1007/bf01704020
    151 rdf:type schema:CreativeWork
    152 sg:pub.10.1007/s00236-003-0120-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017699949
    153 https://doi.org/10.1007/s00236-003-0120-0
    154 rdf:type schema:CreativeWork
    155 grid-institutes:grid.4488.0 schema:alternateName Faculty of Computer Science, Technische Universität Dresden, Mommsenstr. 13, 01062, Dresden, Germany
    156 schema:name Faculty of Computer Science, Technische Universität Dresden, Mommsenstr. 13, 01062, Dresden, Germany
    157 rdf:type schema:Organization
    158 grid-institutes:grid.9008.1 schema:alternateName Department of Foundations of Computer Science, University of Szeged, Árpád tér 2, 6720, Szeged, Hungary
    159 schema:name Department of Foundations of Computer Science, University of Szeged, Árpád tér 2, 6720, Szeged, Hungary
    160 rdf:type schema:Organization
     




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


    ...