Weighted Automata Algorithms View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2009

AUTHORS

Mehryar Mohri

ABSTRACT

Weighted automata and transducers are widely used in modern applications in bioinformatics and text, speech, and image processing. This chapter describes several fundamental weighted automata and shortest-distance algorithms including composition, determinization, minimization, and synchronization, as well as single-source and all-pairs shortest distance algorithms over general semirings. It presents the pseudocode of these algorithms, gives an analysis of their running time complexity, and illustrates their use in some simple cases. Many other complex weighted automata and transducer algorithms used in practice can be obtained by combining these core algorithms. More... »

PAGES

213-254

Book

TITLE

Handbook of Weighted Automata

ISBN

978-3-642-01491-8
978-3-642-01492-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-01492-5_6

DOI

http://dx.doi.org/10.1007/978-3-642-01492-5_6

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Courant Institute of Mathematical Sciences", 
          "id": "https://www.grid.ac/institutes/grid.482020.c", 
          "name": [
            "Courant Institute of Mathematical Sciences, 251 Mercer Street, New York, NY\u00a010012, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mohri", 
        "givenName": "Mehryar", 
        "id": "sg:person.014747403275.19", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014747403275.19"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/s0304-3975(99)00014-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003596936"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/321992.321993", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005748205"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/321105.321107", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006574609"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0304-3975(77)90049-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007813537"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.3115/981658.981661", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011708073"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0304-3975(77)90056-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018441534"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/inco.1995.1071", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021370181"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0304-3975(92)90142-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022358047"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2004.02.049", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032171848"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0304-3975(98)00115-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041671562"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/s0129054102000996", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062896396"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/s0129054103002114", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062896504"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/s0129054105003066", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062896599"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/s0129054107004966", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062896789"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "Weighted automata and transducers are widely used in modern applications in bioinformatics and text, speech, and image processing. This chapter describes several fundamental weighted automata and shortest-distance algorithms including composition, determinization, minimization, and synchronization, as well as single-source and all-pairs shortest distance algorithms over general semirings. It presents the pseudocode of these algorithms, gives an analysis of their running time complexity, and illustrates their use in some simple cases. Many other complex weighted automata and transducer algorithms used in practice can be obtained by combining these core algorithms.", 
    "editor": [
      {
        "familyName": "Droste", 
        "givenName": "Manfred", 
        "type": "Person"
      }, 
      {
        "familyName": "Kuich", 
        "givenName": "Werner", 
        "type": "Person"
      }, 
      {
        "familyName": "Vogler", 
        "givenName": "Heiko", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-01492-5_6", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-01491-8", 
        "978-3-642-01492-5"
      ], 
      "name": "Handbook of Weighted Automata", 
      "type": "Book"
    }, 
    "name": "Weighted Automata Algorithms", 
    "pagination": "213-254", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-01492-5_6"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "349beeb1161b3f57efb2942cd2fa00ad33291b1d628be4663c7ac6c68c7dc9de"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1011042045"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-01492-5_6", 
      "https://app.dimensions.ai/details/publication/pub.1011042045"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T23:50", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8697_00000249.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-642-01492-5_6"
  }
]
 

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-01492-5_6'

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-01492-5_6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-01492-5_6'

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-01492-5_6'


 

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

117 TRIPLES      23 PREDICATES      41 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-01492-5_6 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N6d379dfdbc4c429d9f7ac5fe24a45a29
4 schema:citation https://doi.org/10.1006/inco.1995.1071
5 https://doi.org/10.1016/0304-3975(77)90049-4
6 https://doi.org/10.1016/0304-3975(77)90056-1
7 https://doi.org/10.1016/0304-3975(92)90142-3
8 https://doi.org/10.1016/j.tcs.2004.02.049
9 https://doi.org/10.1016/s0304-3975(98)00115-7
10 https://doi.org/10.1016/s0304-3975(99)00014-6
11 https://doi.org/10.1142/s0129054102000996
12 https://doi.org/10.1142/s0129054103002114
13 https://doi.org/10.1142/s0129054105003066
14 https://doi.org/10.1142/s0129054107004966
15 https://doi.org/10.1145/321105.321107
16 https://doi.org/10.1145/321992.321993
17 https://doi.org/10.3115/981658.981661
18 schema:datePublished 2009
19 schema:datePublishedReg 2009-01-01
20 schema:description Weighted automata and transducers are widely used in modern applications in bioinformatics and text, speech, and image processing. This chapter describes several fundamental weighted automata and shortest-distance algorithms including composition, determinization, minimization, and synchronization, as well as single-source and all-pairs shortest distance algorithms over general semirings. It presents the pseudocode of these algorithms, gives an analysis of their running time complexity, and illustrates their use in some simple cases. Many other complex weighted automata and transducer algorithms used in practice can be obtained by combining these core algorithms.
21 schema:editor N8060a11ea58141babf1e0b4218b3b234
22 schema:genre chapter
23 schema:inLanguage en
24 schema:isAccessibleForFree true
25 schema:isPartOf N8a6f72e95dcc4d53a71720e430247660
26 schema:name Weighted Automata Algorithms
27 schema:pagination 213-254
28 schema:productId N950e6f18518a433aaf19a389473e198b
29 Na1d93058ce0d4bb1af3d18ac9e3f6138
30 Nfec06903e95b416299316eedb61166a1
31 schema:publisher N097508fbb94b45758a777a02f16d746c
32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011042045
33 https://doi.org/10.1007/978-3-642-01492-5_6
34 schema:sdDatePublished 2019-04-15T23:50
35 schema:sdLicense https://scigraph.springernature.com/explorer/license/
36 schema:sdPublisher Nae381e94a18e4647a5626e96fcbd5320
37 schema:url http://link.springer.com/10.1007/978-3-642-01492-5_6
38 sgo:license sg:explorer/license/
39 sgo:sdDataset chapters
40 rdf:type schema:Chapter
41 N097508fbb94b45758a777a02f16d746c schema:location Berlin, Heidelberg
42 schema:name Springer Berlin Heidelberg
43 rdf:type schema:Organisation
44 N23ba08dce45143b6b3bf62ed2ba295f0 rdf:first N9ec93e7e1b644db391be902bd6011748
45 rdf:rest rdf:nil
46 N6d379dfdbc4c429d9f7ac5fe24a45a29 rdf:first sg:person.014747403275.19
47 rdf:rest rdf:nil
48 N8060a11ea58141babf1e0b4218b3b234 rdf:first Nea723053639747f18488bb448f01d8fc
49 rdf:rest Nde44dedd2cb84bb7b4c8676b2d9d9b0d
50 N8a6f72e95dcc4d53a71720e430247660 schema:isbn 978-3-642-01491-8
51 978-3-642-01492-5
52 schema:name Handbook of Weighted Automata
53 rdf:type schema:Book
54 N950e6f18518a433aaf19a389473e198b schema:name doi
55 schema:value 10.1007/978-3-642-01492-5_6
56 rdf:type schema:PropertyValue
57 N9ec93e7e1b644db391be902bd6011748 schema:familyName Vogler
58 schema:givenName Heiko
59 rdf:type schema:Person
60 Na1055a36cc664a05b5b84a946149d3eb schema:familyName Kuich
61 schema:givenName Werner
62 rdf:type schema:Person
63 Na1d93058ce0d4bb1af3d18ac9e3f6138 schema:name readcube_id
64 schema:value 349beeb1161b3f57efb2942cd2fa00ad33291b1d628be4663c7ac6c68c7dc9de
65 rdf:type schema:PropertyValue
66 Nae381e94a18e4647a5626e96fcbd5320 schema:name Springer Nature - SN SciGraph project
67 rdf:type schema:Organization
68 Nde44dedd2cb84bb7b4c8676b2d9d9b0d rdf:first Na1055a36cc664a05b5b84a946149d3eb
69 rdf:rest N23ba08dce45143b6b3bf62ed2ba295f0
70 Nea723053639747f18488bb448f01d8fc schema:familyName Droste
71 schema:givenName Manfred
72 rdf:type schema:Person
73 Nfec06903e95b416299316eedb61166a1 schema:name dimensions_id
74 schema:value pub.1011042045
75 rdf:type schema:PropertyValue
76 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
77 schema:name Information and Computing Sciences
78 rdf:type schema:DefinedTerm
79 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
80 schema:name Computation Theory and Mathematics
81 rdf:type schema:DefinedTerm
82 sg:person.014747403275.19 schema:affiliation https://www.grid.ac/institutes/grid.482020.c
83 schema:familyName Mohri
84 schema:givenName Mehryar
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014747403275.19
86 rdf:type schema:Person
87 https://doi.org/10.1006/inco.1995.1071 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021370181
88 rdf:type schema:CreativeWork
89 https://doi.org/10.1016/0304-3975(77)90049-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007813537
90 rdf:type schema:CreativeWork
91 https://doi.org/10.1016/0304-3975(77)90056-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018441534
92 rdf:type schema:CreativeWork
93 https://doi.org/10.1016/0304-3975(92)90142-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022358047
94 rdf:type schema:CreativeWork
95 https://doi.org/10.1016/j.tcs.2004.02.049 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032171848
96 rdf:type schema:CreativeWork
97 https://doi.org/10.1016/s0304-3975(98)00115-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041671562
98 rdf:type schema:CreativeWork
99 https://doi.org/10.1016/s0304-3975(99)00014-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003596936
100 rdf:type schema:CreativeWork
101 https://doi.org/10.1142/s0129054102000996 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062896396
102 rdf:type schema:CreativeWork
103 https://doi.org/10.1142/s0129054103002114 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062896504
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1142/s0129054105003066 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062896599
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1142/s0129054107004966 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062896789
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1145/321105.321107 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006574609
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1145/321992.321993 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005748205
112 rdf:type schema:CreativeWork
113 https://doi.org/10.3115/981658.981661 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011708073
114 rdf:type schema:CreativeWork
115 https://www.grid.ac/institutes/grid.482020.c schema:alternateName Courant Institute of Mathematical Sciences
116 schema:name Courant Institute of Mathematical Sciences, 251 Mercer Street, New York, NY 10012, USA
117 rdf:type schema:Organization
 




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


...