Minimization of Deterministic Bottom-Up Tree Transducers View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2010

AUTHORS

Sylvia Friese , Helmut Seidl , Sebastian Maneth

ABSTRACT

We show that for every deterministic bottom-up tree transducer, a unique equivalent transducer can be constructed which is minimal. The construction is based on a sequence of normalizing transformations which, among others, guarantee that non-trivial output is produced as early as possible. For a deterministic bottom-up transducer where every state produces either none or infinitely many outputs, the minimal transducer can be constructed in polynomial time. More... »

PAGES

185-196

Book

TITLE

Developments in Language Theory

ISBN

978-3-642-14454-7
978-3-642-14455-4

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-14455-4_18

DOI

http://dx.doi.org/10.1007/978-3-642-14455-4_18

DIMENSIONS

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


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/03", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Chemical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0303", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Macromolecular and Materials Chemistry", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Technische Universit\u00e4t M\u00fcnchen, Garching, Germany", 
          "id": "http://www.grid.ac/institutes/grid.6936.a", 
          "name": [
            "Technische Universit\u00e4t M\u00fcnchen, Garching, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Friese", 
        "givenName": "Sylvia", 
        "id": "sg:person.012523513243.38", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012523513243.38"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Technische Universit\u00e4t M\u00fcnchen, Garching, Germany", 
          "id": "http://www.grid.ac/institutes/grid.6936.a", 
          "name": [
            "Technische Universit\u00e4t M\u00fcnchen, Garching, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Seidl", 
        "givenName": "Helmut", 
        "id": "sg:person.0600150505.21", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0600150505.21"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "NICTA and University of New South Wales, Sydney, Australia", 
          "id": "http://www.grid.ac/institutes/grid.1005.4", 
          "name": [
            "NICTA and University of New South Wales, Sydney, Australia"
          ], 
          "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"
      }
    ], 
    "datePublished": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "We show that for every deterministic bottom-up tree transducer, a unique equivalent transducer can be constructed which is minimal. The construction is based on a sequence of normalizing transformations which, among others, guarantee that non-trivial output is produced as early as possible. For a deterministic bottom-up transducer where every state produces either none or infinitely many outputs, the minimal transducer can be constructed in polynomial time.", 
    "editor": [
      {
        "familyName": "Gao", 
        "givenName": "Yuan", 
        "type": "Person"
      }, 
      {
        "familyName": "Lu", 
        "givenName": "Hanlin", 
        "type": "Person"
      }, 
      {
        "familyName": "Seki", 
        "givenName": "Shinnosuke", 
        "type": "Person"
      }, 
      {
        "familyName": "Yu", 
        "givenName": "Sheng", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-14455-4_18", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-14454-7", 
        "978-3-642-14455-4"
      ], 
      "name": "Developments in Language Theory", 
      "type": "Book"
    }, 
    "keywords": [
      "transducer", 
      "sequence", 
      "bottom", 
      "transformation", 
      "state", 
      "time", 
      "construction", 
      "output", 
      "tree transducers", 
      "minimization", 
      "polynomial time", 
      "deterministic bottom", 
      "unique equivalent transducer", 
      "equivalent transducer", 
      "non-trivial output", 
      "minimal transducer", 
      "Deterministic Bottom-Up Tree Transducers", 
      "Bottom-Up Tree Transducers"
    ], 
    "name": "Minimization of Deterministic Bottom-Up Tree Transducers", 
    "pagination": "185-196", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1018298739"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-14455-4_18"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-14455-4_18", 
      "https://app.dimensions.ai/details/publication/pub.1018298739"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:03", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_287.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-14455-4_18"
  }
]
 

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-14455-4_18'

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-14455-4_18'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-14455-4_18'

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-14455-4_18'


 

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

110 TRIPLES      23 PREDICATES      44 URIs      37 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-14455-4_18 schema:about anzsrc-for:03
2 anzsrc-for:0303
3 schema:author N8378e115b4384c208bf77a0263f49e18
4 schema:datePublished 2010
5 schema:datePublishedReg 2010-01-01
6 schema:description We show that for every deterministic bottom-up tree transducer, a unique equivalent transducer can be constructed which is minimal. The construction is based on a sequence of normalizing transformations which, among others, guarantee that non-trivial output is produced as early as possible. For a deterministic bottom-up transducer where every state produces either none or infinitely many outputs, the minimal transducer can be constructed in polynomial time.
7 schema:editor N2fb129226e43436da28fef3014e99139
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N3694a08650cc49c5abdcf7f637096879
12 schema:keywords Bottom-Up Tree Transducers
13 Deterministic Bottom-Up Tree Transducers
14 bottom
15 construction
16 deterministic bottom
17 equivalent transducer
18 minimal transducer
19 minimization
20 non-trivial output
21 output
22 polynomial time
23 sequence
24 state
25 time
26 transducer
27 transformation
28 tree transducers
29 unique equivalent transducer
30 schema:name Minimization of Deterministic Bottom-Up Tree Transducers
31 schema:pagination 185-196
32 schema:productId N4963dc55467f4f3988f53ca11f104050
33 Nf7bbd00d6f9e48798524f9353a288b50
34 schema:publisher N0e45420d465f416e9d32562df202a28f
35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018298739
36 https://doi.org/10.1007/978-3-642-14455-4_18
37 schema:sdDatePublished 2021-12-01T20:03
38 schema:sdLicense https://scigraph.springernature.com/explorer/license/
39 schema:sdPublisher N5ea1fc253c2945b584f1362e1e8b0901
40 schema:url https://doi.org/10.1007/978-3-642-14455-4_18
41 sgo:license sg:explorer/license/
42 sgo:sdDataset chapters
43 rdf:type schema:Chapter
44 N0e45420d465f416e9d32562df202a28f schema:name Springer Nature
45 rdf:type schema:Organisation
46 N238d9227e4604b298c273c8aa1329320 schema:familyName Lu
47 schema:givenName Hanlin
48 rdf:type schema:Person
49 N2854d7df402a4f909afe006f8edeff7c rdf:first sg:person.0600150505.21
50 rdf:rest Nfd457d19daa948fe82616cf35c478943
51 N2871546aa5bf4fcebf8a0f061c6bc3b7 schema:familyName Seki
52 schema:givenName Shinnosuke
53 rdf:type schema:Person
54 N2fb129226e43436da28fef3014e99139 rdf:first N754c618ea3904e8a929d09aea87bd13f
55 rdf:rest N341142b57f5c4a828a987a9c6e85c10f
56 N341142b57f5c4a828a987a9c6e85c10f rdf:first N238d9227e4604b298c273c8aa1329320
57 rdf:rest N9bb703b7d3334e17a4495a1f1cd6678f
58 N3694a08650cc49c5abdcf7f637096879 schema:isbn 978-3-642-14454-7
59 978-3-642-14455-4
60 schema:name Developments in Language Theory
61 rdf:type schema:Book
62 N4963dc55467f4f3988f53ca11f104050 schema:name doi
63 schema:value 10.1007/978-3-642-14455-4_18
64 rdf:type schema:PropertyValue
65 N5ea1fc253c2945b584f1362e1e8b0901 schema:name Springer Nature - SN SciGraph project
66 rdf:type schema:Organization
67 N6413ea0da73644d4a938151bf02c8c06 schema:familyName Yu
68 schema:givenName Sheng
69 rdf:type schema:Person
70 N754c618ea3904e8a929d09aea87bd13f schema:familyName Gao
71 schema:givenName Yuan
72 rdf:type schema:Person
73 N7e9f25f036d34308a83fbb5d5fb2d34e rdf:first N6413ea0da73644d4a938151bf02c8c06
74 rdf:rest rdf:nil
75 N8378e115b4384c208bf77a0263f49e18 rdf:first sg:person.012523513243.38
76 rdf:rest N2854d7df402a4f909afe006f8edeff7c
77 N9bb703b7d3334e17a4495a1f1cd6678f rdf:first N2871546aa5bf4fcebf8a0f061c6bc3b7
78 rdf:rest N7e9f25f036d34308a83fbb5d5fb2d34e
79 Nf7bbd00d6f9e48798524f9353a288b50 schema:name dimensions_id
80 schema:value pub.1018298739
81 rdf:type schema:PropertyValue
82 Nfd457d19daa948fe82616cf35c478943 rdf:first sg:person.016240662443.33
83 rdf:rest rdf:nil
84 anzsrc-for:03 schema:inDefinedTermSet anzsrc-for:
85 schema:name Chemical Sciences
86 rdf:type schema:DefinedTerm
87 anzsrc-for:0303 schema:inDefinedTermSet anzsrc-for:
88 schema:name Macromolecular and Materials Chemistry
89 rdf:type schema:DefinedTerm
90 sg:person.012523513243.38 schema:affiliation grid-institutes:grid.6936.a
91 schema:familyName Friese
92 schema:givenName Sylvia
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012523513243.38
94 rdf:type schema:Person
95 sg:person.016240662443.33 schema:affiliation grid-institutes:grid.1005.4
96 schema:familyName Maneth
97 schema:givenName Sebastian
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016240662443.33
99 rdf:type schema:Person
100 sg:person.0600150505.21 schema:affiliation grid-institutes:grid.6936.a
101 schema:familyName Seidl
102 schema:givenName Helmut
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0600150505.21
104 rdf:type schema:Person
105 grid-institutes:grid.1005.4 schema:alternateName NICTA and University of New South Wales, Sydney, Australia
106 schema:name NICTA and University of New South Wales, Sydney, Australia
107 rdf:type schema:Organization
108 grid-institutes:grid.6936.a schema:alternateName Technische Universität München, Garching, Germany
109 schema:name Technische Universität München, Garching, Germany
110 rdf:type schema:Organization
 




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


...