Weighted Automata and Weighted Logics View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2009-09-16

AUTHORS

Manfred Droste , Paul Gastin

ABSTRACT

In automata theory, a fundamental result of Büchi and Elgot states that the recognizable languages are precisely the ones definable by sentences of monadic second order logic. We will present a generalization of this result to the context of weighted automata. We develop syntax and semantics of a quantitative logic; like the behaviors of weighted automata, the semantics of sentences of our logic are formal power series describing ‘how often’ the sentence is true for a given word. Our main result shows that if the weights are taken in an arbitrary semiring, then the behaviors of weighted automata are precisely the series definable by sentences of our quantitative logic. We achieve a similar characterization for weighted Büchi automata acting on infinite words, if the underlying semiring satisfies suitable completeness assumptions. Moreover, if the semiring is additively locally finite or locally finite, then natural extensions of our weighted logic still have the same expressive power as weighted automata. More... »

PAGES

175-211

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/20", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Language, Communication and Culture", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/2004", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Linguistics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Institut f\u00fcr Informatik, Universit\u00e4t Leipzig, 04009, Leipzig, Germany", 
          "id": "http://www.grid.ac/institutes/grid.9647.c", 
          "name": [
            "Institut f\u00fcr Informatik, Universit\u00e4t Leipzig, 04009, Leipzig, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Droste", 
        "givenName": "Manfred", 
        "id": "sg:person.010545141652.14", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010545141652.14"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "LSV, ENS Cachan, INRIA, CNRS, 94230, Cachan, France", 
          "id": "http://www.grid.ac/institutes/grid.464035.0", 
          "name": [
            "LSV, ENS Cachan, INRIA, CNRS, 94230, Cachan, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gastin", 
        "givenName": "Paul", 
        "id": "sg:person.014174063211.71", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014174063211.71"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2009-09-16", 
    "datePublishedReg": "2009-09-16", 
    "description": "In automata theory, a fundamental result of B\u00fcchi and Elgot states that the recognizable languages are precisely the ones definable by sentences of monadic second order logic. We will present a generalization of this result to the context of weighted automata. We develop syntax and semantics of a quantitative logic; like the behaviors of weighted automata, the semantics of sentences of our logic are formal power series describing \u2018how often\u2019 the sentence is true for a given word. Our main result shows that if the weights are taken in an arbitrary semiring, then the behaviors of weighted automata are precisely the series definable by sentences of our quantitative logic. We achieve a similar characterization for weighted B\u00fcchi automata acting on infinite words, if the underlying semiring satisfies suitable completeness assumptions. Moreover, if the semiring is additively locally finite or locally finite, then natural extensions of our weighted logic still have the same expressive power as weighted automata.", 
    "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_5", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-01491-8", 
        "978-3-642-01492-5"
      ], 
      "name": "Handbook of Weighted Automata", 
      "type": "Book"
    }, 
    "keywords": [
      "semantics of sentences", 
      "sentences", 
      "words", 
      "infinite words", 
      "language", 
      "behavior", 
      "context", 
      "syntax", 
      "semantics", 
      "theory", 
      "quantitative logic", 
      "results", 
      "generalization", 
      "expressive power", 
      "logic", 
      "assumption", 
      "automata theory", 
      "one", 
      "series", 
      "recognizable languages", 
      "monadic second-order logic", 
      "main results", 
      "B\u00fcchi", 
      "second-order logic", 
      "automata", 
      "power series", 
      "natural extension", 
      "same expressive power", 
      "power", 
      "fundamental results", 
      "order logic", 
      "weight", 
      "characterization", 
      "B\u00fcchi automata", 
      "extension", 
      "weighted automata", 
      "Elgot", 
      "formal power series", 
      "arbitrary semiring", 
      "semirings", 
      "similar characterization", 
      "weighted logic", 
      "completeness assumption"
    ], 
    "name": "Weighted Automata and Weighted Logics", 
    "pagination": "175-211", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1009402049"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-01492-5_5"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-01492-5_5", 
      "https://app.dimensions.ai/details/publication/pub.1009402049"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-06-01T22:32", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220601/entities/gbq_results/chapter/chapter_331.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-01492-5_5"
  }
]
 

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_5'

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_5'

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_5'

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_5'


 

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

123 TRIPLES      23 PREDICATES      68 URIs      61 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-01492-5_5 schema:about anzsrc-for:20
2 anzsrc-for:2004
3 schema:author N727d91cc95f04cce8301011090b9c1a5
4 schema:datePublished 2009-09-16
5 schema:datePublishedReg 2009-09-16
6 schema:description In automata theory, a fundamental result of Büchi and Elgot states that the recognizable languages are precisely the ones definable by sentences of monadic second order logic. We will present a generalization of this result to the context of weighted automata. We develop syntax and semantics of a quantitative logic; like the behaviors of weighted automata, the semantics of sentences of our logic are formal power series describing ‘how often’ the sentence is true for a given word. Our main result shows that if the weights are taken in an arbitrary semiring, then the behaviors of weighted automata are precisely the series definable by sentences of our quantitative logic. We achieve a similar characterization for weighted Büchi automata acting on infinite words, if the underlying semiring satisfies suitable completeness assumptions. Moreover, if the semiring is additively locally finite or locally finite, then natural extensions of our weighted logic still have the same expressive power as weighted automata.
7 schema:editor N250b94e58cc148ad98241519cc75fcd0
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Ndf18a060bcc547a483f5af86bc672701
12 schema:keywords Büchi
13 Büchi automata
14 Elgot
15 arbitrary semiring
16 assumption
17 automata
18 automata theory
19 behavior
20 characterization
21 completeness assumption
22 context
23 expressive power
24 extension
25 formal power series
26 fundamental results
27 generalization
28 infinite words
29 language
30 logic
31 main results
32 monadic second-order logic
33 natural extension
34 one
35 order logic
36 power
37 power series
38 quantitative logic
39 recognizable languages
40 results
41 same expressive power
42 second-order logic
43 semantics
44 semantics of sentences
45 semirings
46 sentences
47 series
48 similar characterization
49 syntax
50 theory
51 weight
52 weighted automata
53 weighted logic
54 words
55 schema:name Weighted Automata and Weighted Logics
56 schema:pagination 175-211
57 schema:productId Nba1faddbed8e4ea8abbd94b9ac3e2d76
58 Nf8603fe7805849b9bace2863aecba4e9
59 schema:publisher Ncfb35c14f94c41ac96f7410dbe2dbeff
60 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009402049
61 https://doi.org/10.1007/978-3-642-01492-5_5
62 schema:sdDatePublished 2022-06-01T22:32
63 schema:sdLicense https://scigraph.springernature.com/explorer/license/
64 schema:sdPublisher N65c070262b034fb4b99376fd1a64ca6a
65 schema:url https://doi.org/10.1007/978-3-642-01492-5_5
66 sgo:license sg:explorer/license/
67 sgo:sdDataset chapters
68 rdf:type schema:Chapter
69 N11b08851b0394f87865fac299097e1b8 schema:familyName Droste
70 schema:givenName Manfred
71 rdf:type schema:Person
72 N15fa825a449648a197aa75b5c2934902 schema:familyName Vogler
73 schema:givenName Heiko
74 rdf:type schema:Person
75 N250b94e58cc148ad98241519cc75fcd0 rdf:first N11b08851b0394f87865fac299097e1b8
76 rdf:rest N65db5fde45224a3cb8dffbfa44298df2
77 N62e80f2ff1fc4fc0858becb7c02c3cad rdf:first N15fa825a449648a197aa75b5c2934902
78 rdf:rest rdf:nil
79 N65c070262b034fb4b99376fd1a64ca6a schema:name Springer Nature - SN SciGraph project
80 rdf:type schema:Organization
81 N65db5fde45224a3cb8dffbfa44298df2 rdf:first Ne806cac515254e9db7a62295ebe99764
82 rdf:rest N62e80f2ff1fc4fc0858becb7c02c3cad
83 N727d91cc95f04cce8301011090b9c1a5 rdf:first sg:person.010545141652.14
84 rdf:rest Nc893e4f9dbd046c2a23bef931d0d8f7b
85 Nba1faddbed8e4ea8abbd94b9ac3e2d76 schema:name dimensions_id
86 schema:value pub.1009402049
87 rdf:type schema:PropertyValue
88 Nc893e4f9dbd046c2a23bef931d0d8f7b rdf:first sg:person.014174063211.71
89 rdf:rest rdf:nil
90 Ncfb35c14f94c41ac96f7410dbe2dbeff schema:name Springer Nature
91 rdf:type schema:Organisation
92 Ndf18a060bcc547a483f5af86bc672701 schema:isbn 978-3-642-01491-8
93 978-3-642-01492-5
94 schema:name Handbook of Weighted Automata
95 rdf:type schema:Book
96 Ne806cac515254e9db7a62295ebe99764 schema:familyName Kuich
97 schema:givenName Werner
98 rdf:type schema:Person
99 Nf8603fe7805849b9bace2863aecba4e9 schema:name doi
100 schema:value 10.1007/978-3-642-01492-5_5
101 rdf:type schema:PropertyValue
102 anzsrc-for:20 schema:inDefinedTermSet anzsrc-for:
103 schema:name Language, Communication and Culture
104 rdf:type schema:DefinedTerm
105 anzsrc-for:2004 schema:inDefinedTermSet anzsrc-for:
106 schema:name Linguistics
107 rdf:type schema:DefinedTerm
108 sg:person.010545141652.14 schema:affiliation grid-institutes:grid.9647.c
109 schema:familyName Droste
110 schema:givenName Manfred
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010545141652.14
112 rdf:type schema:Person
113 sg:person.014174063211.71 schema:affiliation grid-institutes:grid.464035.0
114 schema:familyName Gastin
115 schema:givenName Paul
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014174063211.71
117 rdf:type schema:Person
118 grid-institutes:grid.464035.0 schema:alternateName LSV, ENS Cachan, INRIA, CNRS, 94230, Cachan, France
119 schema:name LSV, ENS Cachan, INRIA, CNRS, 94230, Cachan, France
120 rdf:type schema:Organization
121 grid-institutes:grid.9647.c schema:alternateName Institut für Informatik, Universität Leipzig, 04009, Leipzig, Germany
122 schema:name Institut für Informatik, Universität Leipzig, 04009, Leipzig, Germany
123 rdf:type schema:Organization
 




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


...