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": "2021-11-01T18:50", 
    "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_21.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 Nfaf1ebcf76e44fd6b2663317bf56aeb9
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 N24297b70d1004649ba7a51f099ec9695
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N481188f6edc84d37933b5123288db737
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 N407f04353f76416b815b4276a8f5f97f
35 N88a3f6e2625648b48cb4a4f3cbc0bad8
36 schema:publisher N2a02a8186d194917babf5d23211c3da1
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 2021-11-01T18:50
40 schema:sdLicense https://scigraph.springernature.com/explorer/license/
41 schema:sdPublisher Neb7dbe58613f43a6bc9ef8c38016f5d9
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 N14fa0aa9d5ec4371a416bb7556165f7d schema:familyName Žďárek
47 schema:givenName Jan
48 rdf:type schema:Person
49 N24297b70d1004649ba7a51f099ec9695 rdf:first N7f4555c414a54060967a6a5dd9e03726
50 rdf:rest Nca9ad43ef33d4ac0b8d4225043662335
51 N2a02a8186d194917babf5d23211c3da1 schema:name Springer Nature
52 rdf:type schema:Organisation
53 N407f04353f76416b815b4276a8f5f97f schema:name dimensions_id
54 schema:value pub.1052794246
55 rdf:type schema:PropertyValue
56 N481188f6edc84d37933b5123288db737 schema:isbn 978-3-540-76335-2
57 978-3-540-76336-9
58 schema:name Implementation and Application of Automata
59 rdf:type schema:Book
60 N7f4555c414a54060967a6a5dd9e03726 schema:familyName Holub
61 schema:givenName Jan
62 rdf:type schema:Person
63 N88a3f6e2625648b48cb4a4f3cbc0bad8 schema:name doi
64 schema:value 10.1007/978-3-540-76336-9_12
65 rdf:type schema:PropertyValue
66 Nca9ad43ef33d4ac0b8d4225043662335 rdf:first N14fa0aa9d5ec4371a416bb7556165f7d
67 rdf:rest rdf:nil
68 Ndf5dabd80dc94245bf31369ef3d7b9b5 rdf:first sg:person.016645332751.01
69 rdf:rest Need5c94d10674669b155caed26f4d9fe
70 Neb7dbe58613f43a6bc9ef8c38016f5d9 schema:name Springer Nature - SN SciGraph project
71 rdf:type schema:Organization
72 Need5c94d10674669b155caed26f4d9fe rdf:first sg:person.013420373673.84
73 rdf:rest rdf:nil
74 Nfaf1ebcf76e44fd6b2663317bf56aeb9 rdf:first sg:person.015767576765.59
75 rdf:rest Ndf5dabd80dc94245bf31369ef3d7b9b5
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)


...