Pushing for Weighted Tree Automata View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2011

AUTHORS

Andreas Maletti , Daniel Quernheim

ABSTRACT

Explicit pushing for weighted tree automata over semifields is introduced. A careful selection of the pushing weights allows a normalization of bottom-up deterministic weighted tree automata. Automata in the obtained normal form can be minimized by a simple transformation into an unweighted automaton followed by unweighted minimization. This generalizes results of Mohri and Eisner for deterministic weighted string automata to the tree case. Moreover, the new strategy can also be used to test equivalence of two bottom-up deterministic weighted tree automata M1 and M2 in time O(|M |log|Q|), where |M | = |M1| + |M2| and |Q| is the sum of the number of states of M1 and M2. This improves the previously best running time O(|M1|·|M2|). More... »

PAGES

460-471

Book

TITLE

Mathematical Foundations of Computer Science 2011

ISBN

978-3-642-22992-3
978-3-642-22993-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-22993-0_42

DOI

http://dx.doi.org/10.1007/978-3-642-22993-0_42

DIMENSIONS

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


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/05", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Environmental Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0501", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Ecological Applications", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Institut f\u00fcr Maschinelle Sprachverarbeitung, Universit\u00e4t Stuttgart, Azenbergstra\u00dfe\u00a012, 70174, Stuttgart, Germany", 
          "id": "http://www.grid.ac/institutes/grid.5719.a", 
          "name": [
            "Institut f\u00fcr Maschinelle Sprachverarbeitung, Universit\u00e4t Stuttgart, Azenbergstra\u00dfe\u00a012, 70174, Stuttgart, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Maletti", 
        "givenName": "Andreas", 
        "id": "sg:person.016645332751.01", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016645332751.01"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institut f\u00fcr Maschinelle Sprachverarbeitung, Universit\u00e4t Stuttgart, Azenbergstra\u00dfe\u00a012, 70174, Stuttgart, Germany", 
          "id": "http://www.grid.ac/institutes/grid.5719.a", 
          "name": [
            "Institut f\u00fcr Maschinelle Sprachverarbeitung, Universit\u00e4t Stuttgart, Azenbergstra\u00dfe\u00a012, 70174, Stuttgart, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Quernheim", 
        "givenName": "Daniel", 
        "id": "sg:person.013113560367.55", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013113560367.55"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2011", 
    "datePublishedReg": "2011-01-01", 
    "description": "Explicit pushing for weighted tree automata over semifields is introduced. A careful selection of the pushing weights allows a normalization of bottom-up deterministic weighted tree automata. Automata in the obtained normal form can be minimized by a simple transformation into an unweighted automaton followed by unweighted minimization. This generalizes results of Mohri and Eisner for deterministic weighted string automata to the tree case. Moreover, the new strategy can also be used to test equivalence of two bottom-up deterministic weighted tree automata M1\u00a0and\u00a0M2 in time\u00a0O(|M |log|Q|), where |M |\u2009=\u2009|M1|\u2009+\u2009|M2| and |Q| is the sum of the number of states of M1\u00a0and\u00a0M2. This improves the previously best running time\u00a0O(|M1|\u00b7|M2|).", 
    "editor": [
      {
        "familyName": "Murlak", 
        "givenName": "Filip", 
        "type": "Person"
      }, 
      {
        "familyName": "Sankowski", 
        "givenName": "Piotr", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-22993-0_42", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-22992-3", 
        "978-3-642-22993-0"
      ], 
      "name": "Mathematical Foundations of Computer Science 2011", 
      "type": "Book"
    }, 
    "keywords": [
      "new strategy", 
      "M1", 
      "selection", 
      "bottom", 
      "form", 
      "tree case", 
      "number", 
      "transformation", 
      "strategies", 
      "weight", 
      "m2", 
      "results", 
      "time", 
      "careful selection", 
      "state", 
      "semifields", 
      "normalization", 
      "Mohri", 
      "cases", 
      "sum", 
      "Eisner", 
      "deterministic", 
      "normal form", 
      "automata", 
      "simple transformation", 
      "equivalence", 
      "running time", 
      "minimization", 
      "number of states", 
      "better running time", 
      "tree automata", 
      "Weighted Tree Automata", 
      "normalization of bottom", 
      "unweighted automata", 
      "unweighted minimization", 
      "results of Mohri", 
      "string automata", 
      "tree automata M1", 
      "automata M1"
    ], 
    "name": "Pushing for Weighted Tree Automata", 
    "pagination": "460-471", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1008066261"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-22993-0_42"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-22993-0_42", 
      "https://app.dimensions.ai/details/publication/pub.1008066261"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:56", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_348.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-22993-0_42"
  }
]
 

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-22993-0_42'

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-22993-0_42'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-22993-0_42'

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-22993-0_42'


 

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

111 TRIPLES      23 PREDICATES      65 URIs      58 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-22993-0_42 schema:about anzsrc-for:05
2 anzsrc-for:0501
3 schema:author Nbe8f52e365d2472fa61d1b6719327a55
4 schema:datePublished 2011
5 schema:datePublishedReg 2011-01-01
6 schema:description Explicit pushing for weighted tree automata over semifields is introduced. A careful selection of the pushing weights allows a normalization of bottom-up deterministic weighted tree automata. Automata in the obtained normal form can be minimized by a simple transformation into an unweighted automaton followed by unweighted minimization. This generalizes results of Mohri and Eisner for deterministic weighted string automata to the tree case. Moreover, the new strategy can also be used to test equivalence of two bottom-up deterministic weighted tree automata M1 and M2 in time O(|M |log|Q|), where |M | = |M1| + |M2| and |Q| is the sum of the number of states of M1 and M2. This improves the previously best running time O(|M1|·|M2|).
7 schema:editor N37799635db2249c2bf194230cc78c3d9
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nbd436b2db0984a77a24374d159d52838
12 schema:keywords Eisner
13 M1
14 Mohri
15 Weighted Tree Automata
16 automata
17 automata M1
18 better running time
19 bottom
20 careful selection
21 cases
22 deterministic
23 equivalence
24 form
25 m2
26 minimization
27 new strategy
28 normal form
29 normalization
30 normalization of bottom
31 number
32 number of states
33 results
34 results of Mohri
35 running time
36 selection
37 semifields
38 simple transformation
39 state
40 strategies
41 string automata
42 sum
43 time
44 transformation
45 tree automata
46 tree automata M1
47 tree case
48 unweighted automata
49 unweighted minimization
50 weight
51 schema:name Pushing for Weighted Tree Automata
52 schema:pagination 460-471
53 schema:productId N7e2bb82d3d02419598cb664e132d2c18
54 Nde4c9ade83be47ae9b5ae9c30450fbb6
55 schema:publisher N9333ba1879db4b4fb7bd80de33c92b1b
56 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008066261
57 https://doi.org/10.1007/978-3-642-22993-0_42
58 schema:sdDatePublished 2021-11-01T18:56
59 schema:sdLicense https://scigraph.springernature.com/explorer/license/
60 schema:sdPublisher N0691e43d269044bc96071ca54d7d0385
61 schema:url https://doi.org/10.1007/978-3-642-22993-0_42
62 sgo:license sg:explorer/license/
63 sgo:sdDataset chapters
64 rdf:type schema:Chapter
65 N0691e43d269044bc96071ca54d7d0385 schema:name Springer Nature - SN SciGraph project
66 rdf:type schema:Organization
67 N15c0d10d59d54750bd8759a13ba0cbb2 schema:familyName Murlak
68 schema:givenName Filip
69 rdf:type schema:Person
70 N27065389de6f4c5abb2935297c398aa2 schema:familyName Sankowski
71 schema:givenName Piotr
72 rdf:type schema:Person
73 N28694a5b5dce4567bc3b38bbf6a50216 rdf:first sg:person.013113560367.55
74 rdf:rest rdf:nil
75 N37799635db2249c2bf194230cc78c3d9 rdf:first N15c0d10d59d54750bd8759a13ba0cbb2
76 rdf:rest Nae7531f8a6534781a580d5507bdfa1b4
77 N7e2bb82d3d02419598cb664e132d2c18 schema:name doi
78 schema:value 10.1007/978-3-642-22993-0_42
79 rdf:type schema:PropertyValue
80 N9333ba1879db4b4fb7bd80de33c92b1b schema:name Springer Nature
81 rdf:type schema:Organisation
82 Nae7531f8a6534781a580d5507bdfa1b4 rdf:first N27065389de6f4c5abb2935297c398aa2
83 rdf:rest rdf:nil
84 Nbd436b2db0984a77a24374d159d52838 schema:isbn 978-3-642-22992-3
85 978-3-642-22993-0
86 schema:name Mathematical Foundations of Computer Science 2011
87 rdf:type schema:Book
88 Nbe8f52e365d2472fa61d1b6719327a55 rdf:first sg:person.016645332751.01
89 rdf:rest N28694a5b5dce4567bc3b38bbf6a50216
90 Nde4c9ade83be47ae9b5ae9c30450fbb6 schema:name dimensions_id
91 schema:value pub.1008066261
92 rdf:type schema:PropertyValue
93 anzsrc-for:05 schema:inDefinedTermSet anzsrc-for:
94 schema:name Environmental Sciences
95 rdf:type schema:DefinedTerm
96 anzsrc-for:0501 schema:inDefinedTermSet anzsrc-for:
97 schema:name Ecological Applications
98 rdf:type schema:DefinedTerm
99 sg:person.013113560367.55 schema:affiliation grid-institutes:grid.5719.a
100 schema:familyName Quernheim
101 schema:givenName Daniel
102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013113560367.55
103 rdf:type schema:Person
104 sg:person.016645332751.01 schema:affiliation grid-institutes:grid.5719.a
105 schema:familyName Maletti
106 schema:givenName Andreas
107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016645332751.01
108 rdf:type schema:Person
109 grid-institutes:grid.5719.a schema:alternateName Institut für Maschinelle Sprachverarbeitung, Universität Stuttgart, Azenbergstraße 12, 70174, Stuttgart, Germany
110 schema:name Institut für Maschinelle Sprachverarbeitung, Universität Stuttgart, Azenbergstraße 12, 70174, Stuttgart, Germany
111 rdf:type schema:Organization
 




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


...