Backward and Forward Bisimulation Minimisation of 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 improve an existing bisimulation minimisation algorithm for tree automata by introducing backward and forward bisimulations and developing minimisation algorithms for them. Minimisation via forward bisimulation is also effective for deterministic automata and faster than the previous algorithm. Minimisation via backward bisimulation generalises the previous algorithm and is thus more effective but just as fast. We demonstrate implementations of these algorithms on a typical task in natural language processing. More... »

PAGES

109-121

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-76336-9_12

DOI

http://dx.doi.org/10.1007/978-3-540-76336-9_12

DIMENSIONS

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


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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Dept. of Computing Science, Ume\u00e5 University, S\u201390187 Ume\u00e5, Sweden", 
          "id": "http://www.grid.ac/institutes/grid.12650.30", 
          "name": [
            "Dept. 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 improve an existing bisimulation minimisation algorithm for tree automata by introducing backward and forward bisimulations and developing minimisation algorithms for them. Minimisation via forward bisimulation is also effective for deterministic automata and faster than the previous algorithm. Minimisation via backward bisimulation generalises the previous algorithm and is thus more effective but just as fast. We demonstrate implementations of these algorithms on a typical task in natural language processing.", 
    "editor": [
      {
        "familyName": "Holub", 
        "givenName": "Jan", 
        "type": "Person"
      }, 
      {
        "familyName": "\u017d\u010f\u00e1rek", 
        "givenName": "Jan", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-76336-9_12", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-76335-2", 
        "978-3-540-76336-9"
      ], 
      "name": "Implementation and Application of Automata", 
      "type": "Book"
    }, 
    "keywords": [
      "previous algorithms", 
      "natural language processing", 
      "tree automata", 
      "typical tasks", 
      "language processing", 
      "bisimulation minimisation", 
      "algorithm", 
      "automata", 
      "minimisation algorithm", 
      "bisimulation", 
      "forward bisimulation", 
      "implementation", 
      "task", 
      "minimisation", 
      "processing", 
      "deterministic automata", 
      "Backward", 
      "bisimulation minimisation algorithm", 
      "backward bisimulation", 
      "Forward Bisimulation Minimisation"
    ], 
    "name": "Backward and Forward Bisimulation Minimisation of Tree Automata", 
    "pagination": "109-121", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1052794246"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-76336-9_12"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-76336-9_12", 
      "https://app.dimensions.ai/details/publication/pub.1052794246"
    ], 
    "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_312.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-76336-9_12"
  }
]
 

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-76336-9_12'

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-76336-9_12'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-76336-9_12'

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-76336-9_12'


 

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

105 TRIPLES      23 PREDICATES      46 URIs      39 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-76336-9_12 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N785f74a6e5704a0997962517129472e5
4 schema:datePublished 2007
5 schema:datePublishedReg 2007-01-01
6 schema:description We improve an existing bisimulation minimisation algorithm for tree automata by introducing backward and forward bisimulations and developing minimisation algorithms for them. Minimisation via forward bisimulation is also effective for deterministic automata and faster than the previous algorithm. Minimisation via backward bisimulation generalises the previous algorithm and is thus more effective but just as fast. We demonstrate implementations of these algorithms on a typical task in natural language processing.
7 schema:editor N602c66be307e4a658f7cdf9302eb924f
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nb7c97b9167784bee92317e48f775870a
12 schema:keywords Backward
13 Forward Bisimulation Minimisation
14 algorithm
15 automata
16 backward bisimulation
17 bisimulation
18 bisimulation minimisation
19 bisimulation minimisation algorithm
20 deterministic automata
21 forward bisimulation
22 implementation
23 language processing
24 minimisation
25 minimisation algorithm
26 natural language processing
27 previous algorithms
28 processing
29 task
30 tree automata
31 typical tasks
32 schema:name Backward and Forward Bisimulation Minimisation of Tree Automata
33 schema:pagination 109-121
34 schema:productId N141b712189004fa3aab6076b30039b1b
35 N2c44527ac99b474c80f0039be70c2637
36 schema:publisher N5d7685ac53d8416db50f69e08bc2ac4f
37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052794246
38 https://doi.org/10.1007/978-3-540-76336-9_12
39 schema:sdDatePublished 2022-01-01T19:18
40 schema:sdLicense https://scigraph.springernature.com/explorer/license/
41 schema:sdPublisher N33a1a70ac7d448b49f74b3e11266f590
42 schema:url https://doi.org/10.1007/978-3-540-76336-9_12
43 sgo:license sg:explorer/license/
44 sgo:sdDataset chapters
45 rdf:type schema:Chapter
46 N141b712189004fa3aab6076b30039b1b schema:name doi
47 schema:value 10.1007/978-3-540-76336-9_12
48 rdf:type schema:PropertyValue
49 N20cee07d539443cd9ac03c7913ba9566 rdf:first sg:person.013420373673.84
50 rdf:rest rdf:nil
51 N284d0b759b0044e7b11c8d48f7481a37 rdf:first Ncf308d091c86406697fc56234cdec998
52 rdf:rest rdf:nil
53 N2c44527ac99b474c80f0039be70c2637 schema:name dimensions_id
54 schema:value pub.1052794246
55 rdf:type schema:PropertyValue
56 N33a1a70ac7d448b49f74b3e11266f590 schema:name Springer Nature - SN SciGraph project
57 rdf:type schema:Organization
58 N40463b10d7e641f7bec124339ce36cec schema:familyName Holub
59 schema:givenName Jan
60 rdf:type schema:Person
61 N5d7685ac53d8416db50f69e08bc2ac4f schema:name Springer Nature
62 rdf:type schema:Organisation
63 N602c66be307e4a658f7cdf9302eb924f rdf:first N40463b10d7e641f7bec124339ce36cec
64 rdf:rest N284d0b759b0044e7b11c8d48f7481a37
65 N785f74a6e5704a0997962517129472e5 rdf:first sg:person.015767576765.59
66 rdf:rest N93710eeec2004d17982e285f27e16ed2
67 N93710eeec2004d17982e285f27e16ed2 rdf:first sg:person.016645332751.01
68 rdf:rest N20cee07d539443cd9ac03c7913ba9566
69 Nb7c97b9167784bee92317e48f775870a schema:isbn 978-3-540-76335-2
70 978-3-540-76336-9
71 schema:name Implementation and Application of Automata
72 rdf:type schema:Book
73 Ncf308d091c86406697fc56234cdec998 schema:familyName Žďárek
74 schema:givenName Jan
75 rdf:type schema:Person
76 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
77 schema:name Information and Computing Sciences
78 rdf:type schema:DefinedTerm
79 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
80 schema:name Artificial Intelligence and Image Processing
81 rdf:type schema:DefinedTerm
82 sg:person.013420373673.84 schema:affiliation grid-institutes:grid.42505.36
83 schema:familyName May
84 schema:givenName Jonathan
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013420373673.84
86 rdf:type schema:Person
87 sg:person.015767576765.59 schema:affiliation grid-institutes:grid.12650.30
88 schema:familyName Högberg
89 schema:givenName Johanna
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015767576765.59
91 rdf:type schema:Person
92 sg:person.016645332751.01 schema:affiliation grid-institutes:grid.4488.0
93 schema:familyName Maletti
94 schema:givenName Andreas
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016645332751.01
96 rdf:type schema:Person
97 grid-institutes:grid.12650.30 schema:alternateName Dept. of Computing Science, Umeå University, S–90187 Umeå, Sweden
98 schema:name Dept. of Computing Science, Umeå University, S–90187 Umeå, Sweden
99 rdf:type schema:Organization
100 grid-institutes:grid.42505.36 schema:alternateName Information Sciences Institute, University of Southern California, Marina Del Rey, CA 90292
101 schema:name Information Sciences Institute, University of Southern California, Marina Del Rey, CA 90292
102 rdf:type schema:Organization
103 grid-institutes:grid.4488.0 schema:alternateName Faculty of Computer Science, Technische Universität Dresden, D–01062 Dresden, Germany
104 schema:name Faculty of Computer Science, Technische Universität Dresden, D–01062 Dresden, Germany
105 rdf:type schema:Organization
 




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


...