Weighted Tree Automata and Tree Transducers View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2009-09-16

AUTHORS

Zoltán Fülöp , Heiko Vogler

ABSTRACT

We survey some important results for weighted tree automata and weighted tree transducers over finite ranked trees and semirings as weight structure. In particular, we address closure properties of the class of recognizable tree series, results on the support of such tree series, the determinization of weighted tree automata, pumping lemmata and decidability results, and finite algebraic characterizations of recognizable tree series. We discuss the equivalence between recognizable tree series and equational, rational, and MSO-definable tree series, and we present a comparison of several other models of recognizability. For weighted tree transducers we show composition and decomposition results, an inclusion diagram of some fundamental classes of tree series transformations, and hierarchies obtained by composing weighted tree transducers. We also discuss other models of weighted tree transducers. More... »

PAGES

313-403

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-01492-5_9

DOI

http://dx.doi.org/10.1007/978-3-642-01492-5_9

DIMENSIONS

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


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/06", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Biological Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0699", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Other Biological Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department 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 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, 01062, Dresden, Germany", 
          "id": "http://www.grid.ac/institutes/grid.4488.0", 
          "name": [
            "Faculty of Computer Science, Technische Universit\u00e4t Dresden, 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"
      }
    ], 
    "datePublished": "2009-09-16", 
    "datePublishedReg": "2009-09-16", 
    "description": "We survey some important results for weighted tree automata and weighted tree transducers over finite ranked trees and semirings as weight structure. In particular, we address closure properties of the class of recognizable tree series, results on the support of such tree series, the determinization of weighted tree automata, pumping lemmata and decidability results, and finite algebraic characterizations of recognizable tree series. We discuss the equivalence between recognizable tree series and equational, rational, and MSO-definable tree series, and we present a comparison of several other models of recognizability. For weighted tree transducers we show composition and decomposition results, an inclusion diagram of some fundamental classes of tree series transformations, and hierarchies obtained by composing weighted tree transducers. We also discuss other models of weighted tree transducers.", 
    "editor": [
      {
        "familyName": "Droste", 
        "givenName": "Manfred", 
        "type": "Person"
      }, 
      {
        "familyName": "Kuich", 
        "givenName": "Werner", 
        "type": "Person"
      }, 
      {
        "familyName": "Vogler", 
        "givenName": "Heiko", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-01492-5_9", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-01491-8", 
        "978-3-642-01492-5"
      ], 
      "name": "Handbook of Weighted Automata", 
      "type": "Book"
    }, 
    "keywords": [
      "recognizable tree series", 
      "algebraic characterization", 
      "tree series", 
      "fundamental class", 
      "series transformation", 
      "important results", 
      "closure properties", 
      "decidability results", 
      "decomposition results", 
      "weight structures", 
      "automata", 
      "finite", 
      "lemma", 
      "class", 
      "semirings", 
      "tree transducers", 
      "model", 
      "equivalence", 
      "tree automata", 
      "diagram", 
      "determinization", 
      "results", 
      "transducer", 
      "properties", 
      "transformation", 
      "hierarchy", 
      "series", 
      "structure", 
      "Weighted Tree Automata", 
      "comparison", 
      "trees", 
      "characterization", 
      "recognizability", 
      "composition", 
      "support", 
      "inclusion diagram"
    ], 
    "name": "Weighted Tree Automata and Tree Transducers", 
    "pagination": "313-403", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1013273492"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-01492-5_9"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-01492-5_9", 
      "https://app.dimensions.ai/details/publication/pub.1013273492"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:42", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_218.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-01492-5_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/978-3-642-01492-5_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/978-3-642-01492-5_9'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-01492-5_9'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-01492-5_9'


 

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

116 TRIPLES      23 PREDICATES      61 URIs      54 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-01492-5_9 schema:about anzsrc-for:06
2 anzsrc-for:0699
3 schema:author N36583133cc3942999d351fc5dad52ba1
4 schema:datePublished 2009-09-16
5 schema:datePublishedReg 2009-09-16
6 schema:description We survey some important results for weighted tree automata and weighted tree transducers over finite ranked trees and semirings as weight structure. In particular, we address closure properties of the class of recognizable tree series, results on the support of such tree series, the determinization of weighted tree automata, pumping lemmata and decidability results, and finite algebraic characterizations of recognizable tree series. We discuss the equivalence between recognizable tree series and equational, rational, and MSO-definable tree series, and we present a comparison of several other models of recognizability. For weighted tree transducers we show composition and decomposition results, an inclusion diagram of some fundamental classes of tree series transformations, and hierarchies obtained by composing weighted tree transducers. We also discuss other models of weighted tree transducers.
7 schema:editor N6e1b95422e9c4d7c99e2a1b62eb1aec4
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nba46ec826c5541e28a75cba90aebc92a
12 schema:keywords Weighted Tree Automata
13 algebraic characterization
14 automata
15 characterization
16 class
17 closure properties
18 comparison
19 composition
20 decidability results
21 decomposition results
22 determinization
23 diagram
24 equivalence
25 finite
26 fundamental class
27 hierarchy
28 important results
29 inclusion diagram
30 lemma
31 model
32 properties
33 recognizability
34 recognizable tree series
35 results
36 semirings
37 series
38 series transformation
39 structure
40 support
41 transducer
42 transformation
43 tree automata
44 tree series
45 tree transducers
46 trees
47 weight structures
48 schema:name Weighted Tree Automata and Tree Transducers
49 schema:pagination 313-403
50 schema:productId N55648254fb6846e7877d6e853f51fd77
51 Ne067aad3f4b74fa08b684bce456fb88b
52 schema:publisher N841fa7ea67d84de4b1746cff1e1fe2c9
53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013273492
54 https://doi.org/10.1007/978-3-642-01492-5_9
55 schema:sdDatePublished 2022-05-10T10:42
56 schema:sdLicense https://scigraph.springernature.com/explorer/license/
57 schema:sdPublisher Nfd715181b5ea438db98a8918176456df
58 schema:url https://doi.org/10.1007/978-3-642-01492-5_9
59 sgo:license sg:explorer/license/
60 sgo:sdDataset chapters
61 rdf:type schema:Chapter
62 N2db90ccd875542c1983affe1b8c047fe rdf:first N7c49ecbf03354cccb04a163139c286c4
63 rdf:rest Nf7b9685ea6ac4feba267b0a25bd13d30
64 N36583133cc3942999d351fc5dad52ba1 rdf:first sg:person.014007607055.43
65 rdf:rest N6dc8596790984050a9c65dce0f5e64e5
66 N55648254fb6846e7877d6e853f51fd77 schema:name dimensions_id
67 schema:value pub.1013273492
68 rdf:type schema:PropertyValue
69 N6dc8596790984050a9c65dce0f5e64e5 rdf:first sg:person.014562633673.93
70 rdf:rest rdf:nil
71 N6e1b95422e9c4d7c99e2a1b62eb1aec4 rdf:first Ne88765b06c2243f7991fe73c366046c5
72 rdf:rest N2db90ccd875542c1983affe1b8c047fe
73 N7c49ecbf03354cccb04a163139c286c4 schema:familyName Kuich
74 schema:givenName Werner
75 rdf:type schema:Person
76 N841fa7ea67d84de4b1746cff1e1fe2c9 schema:name Springer Nature
77 rdf:type schema:Organisation
78 Nba3cc01572ad45e598e3294b18f5611f schema:familyName Vogler
79 schema:givenName Heiko
80 rdf:type schema:Person
81 Nba46ec826c5541e28a75cba90aebc92a schema:isbn 978-3-642-01491-8
82 978-3-642-01492-5
83 schema:name Handbook of Weighted Automata
84 rdf:type schema:Book
85 Ne067aad3f4b74fa08b684bce456fb88b schema:name doi
86 schema:value 10.1007/978-3-642-01492-5_9
87 rdf:type schema:PropertyValue
88 Ne88765b06c2243f7991fe73c366046c5 schema:familyName Droste
89 schema:givenName Manfred
90 rdf:type schema:Person
91 Nf7b9685ea6ac4feba267b0a25bd13d30 rdf:first Nba3cc01572ad45e598e3294b18f5611f
92 rdf:rest rdf:nil
93 Nfd715181b5ea438db98a8918176456df schema:name Springer Nature - SN SciGraph project
94 rdf:type schema:Organization
95 anzsrc-for:06 schema:inDefinedTermSet anzsrc-for:
96 schema:name Biological Sciences
97 rdf:type schema:DefinedTerm
98 anzsrc-for:0699 schema:inDefinedTermSet anzsrc-for:
99 schema:name Other Biological Sciences
100 rdf:type schema:DefinedTerm
101 sg:person.014007607055.43 schema:affiliation grid-institutes:grid.9008.1
102 schema:familyName Fülöp
103 schema:givenName Zoltán
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014007607055.43
105 rdf:type schema:Person
106 sg:person.014562633673.93 schema:affiliation grid-institutes:grid.4488.0
107 schema:familyName Vogler
108 schema:givenName Heiko
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014562633673.93
110 rdf:type schema:Person
111 grid-institutes:grid.4488.0 schema:alternateName Faculty of Computer Science, Technische Universität Dresden, 01062, Dresden, Germany
112 schema:name Faculty of Computer Science, Technische Universität Dresden, 01062, Dresden, Germany
113 rdf:type schema:Organization
114 grid-institutes:grid.9008.1 schema:alternateName Department of Computer Science, University of Szeged, Árpád tér 2., 6720, Szeged, Hungary
115 schema:name Department of Computer Science, University of Szeged, Árpád tér 2., 6720, Szeged, Hungary
116 rdf:type schema:Organization
 




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


...