Ontology type: schema:Chapter
2016-02-26
AUTHORSHeiko Vogler , Manfred Droste , Luisa Herrmann
ABSTRACTWe introduce a weighted MSO-logic in which one outermost existential quantification over behaviours of a storage type is allowed. As weight structures we take unital valuation monoids which include all semirings, bounded lattices, and computations of average or discounted costs. Each formula is interpreted over finite words yielding elements in the weight structure. We prove that this logic is expressively equivalent to weighted automata with storage. In particular, this implies a Büchi-Elgot-Trakhtenbrot Theorem for weighted iterated pushdown languages. For this choice of storage type, the satisfiability problem of the logic is decidable for each bounded lattice provided that its infimum is computable. More... »
PAGES127-139
Language and Automata Theory and Applications
ISBN
978-3-319-29999-0
978-3-319-30000-9
http://scigraph.springernature.com/pub.10.1007/978-3-319-30000-9_10
DOIhttp://dx.doi.org/10.1007/978-3-319-30000-9_10
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1014710697
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/15",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Commerce, Management, Tourism and Services",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1502",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Banking, Finance and Investment",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Faculty of Computer Science, Technische Universit\u00e4t Dresden, Dresden, Germany",
"id": "http://www.grid.ac/institutes/grid.4488.0",
"name": [
"Faculty of Computer Science, Technische Universit\u00e4t Dresden, Dresden, Germany"
],
"type": "Organization"
},
"familyName": "Vogler",
"givenName": "Heiko",
"id": "sg:person.014562633673.93",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014562633673.93"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Institut F\u00fcr Informatik, Universit\u00e4t Leipzig, Leipzig, Germany",
"id": "http://www.grid.ac/institutes/grid.9647.c",
"name": [
"Institut F\u00fcr Informatik, Universit\u00e4t Leipzig, 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": "Faculty of Computer Science, Technische Universit\u00e4t Dresden, Dresden, Germany",
"id": "http://www.grid.ac/institutes/grid.4488.0",
"name": [
"Faculty of Computer Science, Technische Universit\u00e4t Dresden, Dresden, Germany"
],
"type": "Organization"
},
"familyName": "Herrmann",
"givenName": "Luisa",
"id": "sg:person.010752400543.10",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010752400543.10"
],
"type": "Person"
}
],
"datePublished": "2016-02-26",
"datePublishedReg": "2016-02-26",
"description": "We introduce a weighted MSO-logic in which one outermost existential quantification over behaviours of a storage type is allowed. As weight structures we take unital valuation monoids which include all semirings, bounded lattices, and computations of average or discounted costs. Each formula is interpreted over finite words yielding elements in the weight structure. We prove that this logic is expressively equivalent to weighted automata with storage. In particular, this implies a B\u00fcchi-Elgot-Trakhtenbrot Theorem for weighted iterated pushdown languages. For this choice of storage type, the satisfiability problem of the logic is decidable for each bounded lattice provided that its infimum is computable.",
"editor": [
{
"familyName": "Dediu",
"givenName": "Adrian-Horia",
"type": "Person"
},
{
"familyName": "Janou\u0161ek",
"givenName": "Jan",
"type": "Person"
},
{
"familyName": "Mart\u00edn-Vide",
"givenName": "Carlos",
"type": "Person"
},
{
"familyName": "Truthe",
"givenName": "Bianca",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-319-30000-9_10",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-319-29999-0",
"978-3-319-30000-9"
],
"name": "Language and Automata Theory and Applications",
"type": "Book"
},
"keywords": [
"Trakhtenbrot Theorem",
"weight structures",
"theorem",
"B\u00fcchi-Elgot",
"MSO logic",
"satisfiability problem",
"lattice",
"finite words",
"semirings",
"infimum",
"monoids",
"computation",
"formula",
"existential quantification",
"automata",
"problem",
"structure",
"behavior",
"logic",
"storage types",
"types",
"choice",
"cost",
"elements",
"valuation monoids",
"quantification",
"storage",
"pushdown languages",
"words",
"language",
"storage behavior"
],
"name": "A Weighted MSO Logic with Storage Behaviour and Its B\u00fcchi-Elgot-Trakhtenbrot Theorem",
"pagination": "127-139",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1014710697"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-319-30000-9_10"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-319-30000-9_10",
"https://app.dimensions.ai/details/publication/pub.1014710697"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-05-10T10:47",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_315.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-319-30000-9_10"
}
]
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-319-30000-9_10'
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-319-30000-9_10'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-30000-9_10'
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-319-30000-9_10'
This table displays all metadata directly associated to this object as RDF triples.
123 TRIPLES
23 PREDICATES
56 URIs
49 LITERALS
7 BLANK NODES