Bisimulation Minimisation for Weighted Tree Automata View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2007

AUTHORS

Johanna Högberg , Andreas Maletti , Jonathan May

ABSTRACT

We generalise existing forward and backward bisimulation minimisation algorithms for tree automata to weighted tree automata. The obtained algorithms work for all semirings and retain the time complexity of their unweighted variants for all additively cancellative semirings. On all other semirings the time complexity is slightly higher (linear instead of logarithmic in the number of states). We discuss implementations of these algorithms on a typical task in natural language processing. More... »

PAGES

229-241

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-73208-2_23

DOI

http://dx.doi.org/10.1007/978-3-540-73208-2_23

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computing Science, Ume\u00e5 University, S\u201390187 Ume\u00e5, Sweden", 
          "id": "http://www.grid.ac/institutes/grid.12650.30", 
          "name": [
            "Department of Computing Science, Ume\u00e5 University, S\u201390187 Ume\u00e5, Sweden"
          ], 
          "type": "Organization"
        }, 
        "familyName": "H\u00f6gberg", 
        "givenName": "Johanna", 
        "id": "sg:person.015767576765.59", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015767576765.59"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Faculty of Computer Science, Technische Universit\u00e4t Dresden, D\u201301062 Dresden, Germany", 
          "id": "http://www.grid.ac/institutes/grid.4488.0", 
          "name": [
            "Faculty of Computer Science, Technische Universit\u00e4t Dresden, D\u201301062 Dresden, 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": "Information Sciences Institute, University of Southern California, Marina Del Rey, CA 90292", 
          "id": "http://www.grid.ac/institutes/grid.42505.36", 
          "name": [
            "Information Sciences Institute, University of Southern California, Marina Del Rey, CA 90292"
          ], 
          "type": "Organization"
        }, 
        "familyName": "May", 
        "givenName": "Jonathan", 
        "id": "sg:person.013420373673.84", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013420373673.84"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2007", 
    "datePublishedReg": "2007-01-01", 
    "description": "We generalise existing forward and backward bisimulation minimisation algorithms for tree automata to weighted tree automata. The obtained algorithms work for all semirings and retain the time complexity of their unweighted variants for all additively cancellative semirings. On all other semirings the time complexity is slightly higher (linear instead of logarithmic in the number of states). We discuss implementations of these algorithms on a typical task in natural language processing.", 
    "editor": [
      {
        "familyName": "Harju", 
        "givenName": "Tero", 
        "type": "Person"
      }, 
      {
        "familyName": "Karhum\u00e4ki", 
        "givenName": "Juhani", 
        "type": "Person"
      }, 
      {
        "familyName": "Lepist\u00f6", 
        "givenName": "Arto", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-73208-2_23", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-73207-5", 
        "978-3-540-73208-2"
      ], 
      "name": "Developments in Language Theory", 
      "type": "Book"
    }, 
    "keywords": [
      "time complexity", 
      "natural language processing", 
      "tree automata", 
      "typical tasks", 
      "language processing", 
      "bisimulation minimisation", 
      "Weighted Tree Automata", 
      "unweighted variant", 
      "algorithm", 
      "automata", 
      "complexity", 
      "minimisation algorithm", 
      "semirings", 
      "implementation", 
      "task", 
      "processing", 
      "minimisation", 
      "variants", 
      "backward bisimulation minimisation algorithms", 
      "bisimulation minimisation algorithms", 
      "cancellative semirings"
    ], 
    "name": "Bisimulation Minimisation for Weighted Tree Automata", 
    "pagination": "229-241", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1033449164"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-73208-2_23"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-73208-2_23", 
      "https://app.dimensions.ai/details/publication/pub.1033449164"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:06", 
    "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_103.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-73208-2_23"
  }
]
 

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-540-73208-2_23'

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-540-73208-2_23'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-73208-2_23'

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-540-73208-2_23'


 

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

111 TRIPLES      23 PREDICATES      47 URIs      40 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-73208-2_23 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N925080cd0f4a4358939f73968fc017cf
4 schema:datePublished 2007
5 schema:datePublishedReg 2007-01-01
6 schema:description We generalise existing forward and backward bisimulation minimisation algorithms for tree automata to weighted tree automata. The obtained algorithms work for all semirings and retain the time complexity of their unweighted variants for all additively cancellative semirings. On all other semirings the time complexity is slightly higher (linear instead of logarithmic in the number of states). We discuss implementations of these algorithms on a typical task in natural language processing.
7 schema:editor Ndff55e706f424b049ab2803566601764
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N135ce14b24ea497f932ad80503086bc0
12 schema:keywords Weighted Tree Automata
13 algorithm
14 automata
15 backward bisimulation minimisation algorithms
16 bisimulation minimisation
17 bisimulation minimisation algorithms
18 cancellative semirings
19 complexity
20 implementation
21 language processing
22 minimisation
23 minimisation algorithm
24 natural language processing
25 processing
26 semirings
27 task
28 time complexity
29 tree automata
30 typical tasks
31 unweighted variant
32 variants
33 schema:name Bisimulation Minimisation for Weighted Tree Automata
34 schema:pagination 229-241
35 schema:productId Nabbcf05664df44cdafe83221de2a4dad
36 Nf26a3b2c6af84a6f94615bf856a74228
37 schema:publisher Nc8daa9d7bd564e7dbcd75d9868353dce
38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033449164
39 https://doi.org/10.1007/978-3-540-73208-2_23
40 schema:sdDatePublished 2022-01-01T19:06
41 schema:sdLicense https://scigraph.springernature.com/explorer/license/
42 schema:sdPublisher N73d856f83f7b44f4899403fdc305d7f0
43 schema:url https://doi.org/10.1007/978-3-540-73208-2_23
44 sgo:license sg:explorer/license/
45 sgo:sdDataset chapters
46 rdf:type schema:Chapter
47 N135ce14b24ea497f932ad80503086bc0 schema:isbn 978-3-540-73207-5
48 978-3-540-73208-2
49 schema:name Developments in Language Theory
50 rdf:type schema:Book
51 N1cf0f747b4db4c8787a92ef2fb23af3b rdf:first Ne66586b2b12a4333a2de85e2865574b5
52 rdf:rest N58c1191a0e884ac6b44df8fe6ba6cbbd
53 N38fcbbd55458431ea8d3bd198974392c rdf:first sg:person.016645332751.01
54 rdf:rest Nfad91ab66d0c40499e837510d8c78da4
55 N55edee06f5214ce3a4d877186c13d095 schema:familyName Lepistö
56 schema:givenName Arto
57 rdf:type schema:Person
58 N58c1191a0e884ac6b44df8fe6ba6cbbd rdf:first N55edee06f5214ce3a4d877186c13d095
59 rdf:rest rdf:nil
60 N73d856f83f7b44f4899403fdc305d7f0 schema:name Springer Nature - SN SciGraph project
61 rdf:type schema:Organization
62 N925080cd0f4a4358939f73968fc017cf rdf:first sg:person.015767576765.59
63 rdf:rest N38fcbbd55458431ea8d3bd198974392c
64 Nabbcf05664df44cdafe83221de2a4dad schema:name dimensions_id
65 schema:value pub.1033449164
66 rdf:type schema:PropertyValue
67 Nb9588375f5804b84b73890f4a6a72184 schema:familyName Harju
68 schema:givenName Tero
69 rdf:type schema:Person
70 Nc8daa9d7bd564e7dbcd75d9868353dce schema:name Springer Nature
71 rdf:type schema:Organisation
72 Ndff55e706f424b049ab2803566601764 rdf:first Nb9588375f5804b84b73890f4a6a72184
73 rdf:rest N1cf0f747b4db4c8787a92ef2fb23af3b
74 Ne66586b2b12a4333a2de85e2865574b5 schema:familyName Karhumäki
75 schema:givenName Juhani
76 rdf:type schema:Person
77 Nf26a3b2c6af84a6f94615bf856a74228 schema:name doi
78 schema:value 10.1007/978-3-540-73208-2_23
79 rdf:type schema:PropertyValue
80 Nfad91ab66d0c40499e837510d8c78da4 rdf:first sg:person.013420373673.84
81 rdf:rest rdf:nil
82 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
83 schema:name Information and Computing Sciences
84 rdf:type schema:DefinedTerm
85 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
86 schema:name Computation Theory and Mathematics
87 rdf:type schema:DefinedTerm
88 sg:person.013420373673.84 schema:affiliation grid-institutes:grid.42505.36
89 schema:familyName May
90 schema:givenName Jonathan
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013420373673.84
92 rdf:type schema:Person
93 sg:person.015767576765.59 schema:affiliation grid-institutes:grid.12650.30
94 schema:familyName Högberg
95 schema:givenName Johanna
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015767576765.59
97 rdf:type schema:Person
98 sg:person.016645332751.01 schema:affiliation grid-institutes:grid.4488.0
99 schema:familyName Maletti
100 schema:givenName Andreas
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016645332751.01
102 rdf:type schema:Person
103 grid-institutes:grid.12650.30 schema:alternateName Department of Computing Science, Umeå University, S–90187 Umeå, Sweden
104 schema:name Department of Computing Science, Umeå University, S–90187 Umeå, Sweden
105 rdf:type schema:Organization
106 grid-institutes:grid.42505.36 schema:alternateName Information Sciences Institute, University of Southern California, Marina Del Rey, CA 90292
107 schema:name Information Sciences Institute, University of Southern California, Marina Del Rey, CA 90292
108 rdf:type schema:Organization
109 grid-institutes:grid.4488.0 schema:alternateName Faculty of Computer Science, Technische Universität Dresden, D–01062 Dresden, Germany
110 schema:name Faculty of Computer Science, Technische Universität Dresden, D–01062 Dresden, Germany
111 rdf:type schema:Organization
 




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


...