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": "2022-01-01T19:26", 
    "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_64.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 N8b630381d4614637967e1f22dbe78a38
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 N184e6bd14c4b40e5921491f35509815e
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nb80a0e7c0dee4cb48e68652b835d18fd
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 N18a12c88d75947dfb5b9130de3d175ac
54 Nc718be3dc6664e53ad5342a411220737
55 schema:publisher N6256add9908d4dd4ab9b595ee1fcb8c8
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 2022-01-01T19:26
59 schema:sdLicense https://scigraph.springernature.com/explorer/license/
60 schema:sdPublisher Nd6bec3cdbc8f4e0099f9e09fef8c302b
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 N184e6bd14c4b40e5921491f35509815e rdf:first N7cb48acc31874cd5afff388cb0b17afa
66 rdf:rest Nfc92cc4bc2eb40a9abcf4551727d7054
67 N18a12c88d75947dfb5b9130de3d175ac schema:name dimensions_id
68 schema:value pub.1008066261
69 rdf:type schema:PropertyValue
70 N6256add9908d4dd4ab9b595ee1fcb8c8 schema:name Springer Nature
71 rdf:type schema:Organisation
72 N77a4a70aab814a899b795c398728a596 rdf:first sg:person.013113560367.55
73 rdf:rest rdf:nil
74 N7cb48acc31874cd5afff388cb0b17afa schema:familyName Murlak
75 schema:givenName Filip
76 rdf:type schema:Person
77 N8b630381d4614637967e1f22dbe78a38 rdf:first sg:person.016645332751.01
78 rdf:rest N77a4a70aab814a899b795c398728a596
79 Nb80a0e7c0dee4cb48e68652b835d18fd schema:isbn 978-3-642-22992-3
80 978-3-642-22993-0
81 schema:name Mathematical Foundations of Computer Science 2011
82 rdf:type schema:Book
83 Nc718be3dc6664e53ad5342a411220737 schema:name doi
84 schema:value 10.1007/978-3-642-22993-0_42
85 rdf:type schema:PropertyValue
86 Nd6bec3cdbc8f4e0099f9e09fef8c302b schema:name Springer Nature - SN SciGraph project
87 rdf:type schema:Organization
88 Nf55348d486af4cf8bb180ec4639e497a schema:familyName Sankowski
89 schema:givenName Piotr
90 rdf:type schema:Person
91 Nfc92cc4bc2eb40a9abcf4551727d7054 rdf:first Nf55348d486af4cf8bb180ec4639e497a
92 rdf:rest rdf:nil
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)


...