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": "2021-11-01T18:57", 
    "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_35.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 Nf6b82c56667d4ce9be9e697814c2ad0c
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 N0e230b694c2343c2bcf9f771e59140d1
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N6a4e7571b9224ebda6f6ff4996043dbe
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 N4c2cd613e25c435da410199e4a068ed5
36 N6ac9b98d80704da3ba4c2b0b23f75442
37 schema:publisher Ndf2adc574ba04f8d8844644b6ab54bb7
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 2021-11-01T18:57
41 schema:sdLicense https://scigraph.springernature.com/explorer/license/
42 schema:sdPublisher Nfc21aa9adabf44fca02f417122d45c90
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 N0e230b694c2343c2bcf9f771e59140d1 rdf:first Neaabf48317244beb9c0f201c3e5f37a3
48 rdf:rest N6b6e47d7787a412183aab541e707e54f
49 N40c8093bab754a2b84043a2863d28d68 rdf:first sg:person.013420373673.84
50 rdf:rest rdf:nil
51 N4c2cd613e25c435da410199e4a068ed5 schema:name dimensions_id
52 schema:value pub.1033449164
53 rdf:type schema:PropertyValue
54 N6a4e7571b9224ebda6f6ff4996043dbe schema:isbn 978-3-540-73207-5
55 978-3-540-73208-2
56 schema:name Developments in Language Theory
57 rdf:type schema:Book
58 N6ac9b98d80704da3ba4c2b0b23f75442 schema:name doi
59 schema:value 10.1007/978-3-540-73208-2_23
60 rdf:type schema:PropertyValue
61 N6b6e47d7787a412183aab541e707e54f rdf:first N74199166392c4f9489f837c2288af636
62 rdf:rest Ne1bd8a7f3c0447608a708e19906cf0f8
63 N74199166392c4f9489f837c2288af636 schema:familyName Karhumäki
64 schema:givenName Juhani
65 rdf:type schema:Person
66 Nbe2f85062c2748c9810176ff551a241a schema:familyName Lepistö
67 schema:givenName Arto
68 rdf:type schema:Person
69 Nd44297d7841941a295ad1ca2523504c4 rdf:first sg:person.016645332751.01
70 rdf:rest N40c8093bab754a2b84043a2863d28d68
71 Ndf2adc574ba04f8d8844644b6ab54bb7 schema:name Springer Nature
72 rdf:type schema:Organisation
73 Ne1bd8a7f3c0447608a708e19906cf0f8 rdf:first Nbe2f85062c2748c9810176ff551a241a
74 rdf:rest rdf:nil
75 Neaabf48317244beb9c0f201c3e5f37a3 schema:familyName Harju
76 schema:givenName Tero
77 rdf:type schema:Person
78 Nf6b82c56667d4ce9be9e697814c2ad0c rdf:first sg:person.015767576765.59
79 rdf:rest Nd44297d7841941a295ad1ca2523504c4
80 Nfc21aa9adabf44fca02f417122d45c90 schema:name Springer Nature - SN SciGraph project
81 rdf:type schema:Organization
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)


...