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": "2022-01-01T19:18", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_305.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 N41c9ea62a3414dadbe702dedcc0f33cf
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 N78fa6e49babc4018814ae3b95c971b61
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Naa3ef16f2f054539aa721b3f70f8b447
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 N2a3ef0765da443eea27a8401e5b953f1
33 Nc3114ad882d24e149e739072ec2e585c
34 schema:publisher Ndd1676ae305c4316ba3668f8d834bdaa
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 2022-01-01T19:18
38 schema:sdLicense https://scigraph.springernature.com/explorer/license/
39 schema:sdPublisher N6afa464294dc4b7c882de59f25d437e9
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 N1658d9cc55de4275be1072f3eafb32e7 rdf:first Na702b7e05e4c466faaf220251f297f9b
45 rdf:rest N4b1f7403ec9b4e6bb28d94cfc8c42c07
46 N2a3ef0765da443eea27a8401e5b953f1 schema:name doi
47 schema:value 10.1007/978-3-642-14455-4_18
48 rdf:type schema:PropertyValue
49 N3de49b4279d94e9598615c0a6979bd3c rdf:first sg:person.016240662443.33
50 rdf:rest rdf:nil
51 N41c9ea62a3414dadbe702dedcc0f33cf rdf:first sg:person.012523513243.38
52 rdf:rest N9c59148de03d4029abf63ad0929d9126
53 N4b1f7403ec9b4e6bb28d94cfc8c42c07 rdf:first Nab7d259477e54d729dba2426bb9b497a
54 rdf:rest rdf:nil
55 N6afa464294dc4b7c882de59f25d437e9 schema:name Springer Nature - SN SciGraph project
56 rdf:type schema:Organization
57 N78fa6e49babc4018814ae3b95c971b61 rdf:first N79bcd56564ae45f78098e37e63419da9
58 rdf:rest Nd3f13ccff9394f37a4d30e3f1ca69403
59 N79bcd56564ae45f78098e37e63419da9 schema:familyName Gao
60 schema:givenName Yuan
61 rdf:type schema:Person
62 N9c59148de03d4029abf63ad0929d9126 rdf:first sg:person.0600150505.21
63 rdf:rest N3de49b4279d94e9598615c0a6979bd3c
64 Na30bec8f65dd458bbec02ef5af0a0be3 schema:familyName Lu
65 schema:givenName Hanlin
66 rdf:type schema:Person
67 Na702b7e05e4c466faaf220251f297f9b schema:familyName Seki
68 schema:givenName Shinnosuke
69 rdf:type schema:Person
70 Naa3ef16f2f054539aa721b3f70f8b447 schema:isbn 978-3-642-14454-7
71 978-3-642-14455-4
72 schema:name Developments in Language Theory
73 rdf:type schema:Book
74 Nab7d259477e54d729dba2426bb9b497a schema:familyName Yu
75 schema:givenName Sheng
76 rdf:type schema:Person
77 Nc3114ad882d24e149e739072ec2e585c schema:name dimensions_id
78 schema:value pub.1018298739
79 rdf:type schema:PropertyValue
80 Nd3f13ccff9394f37a4d30e3f1ca69403 rdf:first Na30bec8f65dd458bbec02ef5af0a0be3
81 rdf:rest N1658d9cc55de4275be1072f3eafb32e7
82 Ndd1676ae305c4316ba3668f8d834bdaa schema:name Springer Nature
83 rdf:type schema:Organisation
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)


...