Ontology type: schema:Chapter Open Access: True
2009-09-16
AUTHORS ABSTRACTIn 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... »
PAGES175-211
Handbook of Weighted Automata
ISBN
978-3-642-01491-8
978-3-642-01492-5
http://scigraph.springernature.com/pub.10.1007/978-3-642-01492-5_5
DOIhttp://dx.doi.org/10.1007/978-3-642-01492-5_5
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1009402049
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
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 |