2009-06-27
AUTHORS ABSTRACTWe define a weighted monadic second order logic for unranked trees and the concept of weighted unranked tree automata, and we investigate the expressive power of these two concepts. We show that weighted tree automata and a syntactically restricted weighted MSO-logic have the same expressive power in case the semiring is commutative or in case we deal only with ranked trees, but, surprisingly, not in general. This demonstrates a crucial difference between the theories of ranked trees and unranked trees in the weighted case. More... »
PAGES23-47
http://scigraph.springernature.com/pub.10.1007/s00224-009-9224-4
DOIhttp://dx.doi.org/10.1007/s00224-009-9224-4
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1045410699
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/01",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Mathematical Sciences",
"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"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Applied Mathematics",
"type": "DefinedTerm"
},
{
"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/0805",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Distributed Computing",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Institute of Computer Science, Leipzig University, 04109, Leipzig, Germany",
"id": "http://www.grid.ac/institutes/grid.9647.c",
"name": [
"Institute of Computer Science, Leipzig University, 04109, 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": "Department of Computer Science, Technische Universit\u00e4t Dresden, 01062, Dresden, Germany",
"id": "http://www.grid.ac/institutes/grid.4488.0",
"name": [
"Department of Computer Science, Technische Universit\u00e4t Dresden, 01062, 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"
}
],
"citation": [
{
"id": "sg:pub.10.1007/978-3-540-70583-3_19",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1031990544",
"https://doi.org/10.1007/978-3-540-70583-3_19"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-59126-6_1",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1000867424",
"https://doi.org/10.1007/978-3-642-59126-6_1"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-59136-5_9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1038237872",
"https://doi.org/10.1007/978-3-642-59136-5_9"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-45793-3_2",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1002630146",
"https://doi.org/10.1007/3-540-45793-3_2"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11523468_4",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1046282968",
"https://doi.org/10.1007/11523468_4"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-01492-5_9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1013273492",
"https://doi.org/10.1007/978-3-642-01492-5_9"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-76336-9_9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1025393494",
"https://doi.org/10.1007/978-3-540-76336-9_9"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-18690-5_1",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1001247930",
"https://doi.org/10.1007/978-3-642-18690-5_1"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s00224-009-9225-3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1046469438",
"https://doi.org/10.1007/s00224-009-9225-3"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-73208-2_31",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1039600070",
"https://doi.org/10.1007/978-3-540-73208-2_31"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11753728_25",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1028313790",
"https://doi.org/10.1007/11753728_25"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-73235-5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1109710706",
"https://doi.org/10.1007/978-3-642-73235-5"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11523468_42",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1003892152",
"https://doi.org/10.1007/11523468_42"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-01492-5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1005381459",
"https://doi.org/10.1007/978-3-642-01492-5"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-27836-8_94",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1041874008",
"https://doi.org/10.1007/978-3-540-27836-8_94"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-01492-5_5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1009402049",
"https://doi.org/10.1007/978-3-642-01492-5_5"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-69959-7",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1017490034",
"https://doi.org/10.1007/978-3-642-69959-7"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01691346",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1038809008",
"https://doi.org/10.1007/bf01691346"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-1-4612-6264-0",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1046944411",
"https://doi.org/10.1007/978-1-4612-6264-0"
],
"type": "CreativeWork"
}
],
"datePublished": "2009-06-27",
"datePublishedReg": "2009-06-27",
"description": "We define a weighted monadic second order logic for unranked trees and the concept of weighted unranked tree automata, and we investigate the expressive power of these two concepts. We show that weighted tree automata and a syntactically restricted weighted MSO-logic have the same expressive power in case the semiring is commutative or in case we deal only with ranked trees, but, surprisingly, not in general. This demonstrates a crucial difference between the theories of ranked trees and unranked trees in the weighted case.",
"genre": "article",
"id": "sg:pub.10.1007/s00224-009-9224-4",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": [
{
"id": "sg:journal.1052098",
"issn": [
"1432-4350",
"1433-0490"
],
"name": "Theory of Computing Systems",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "1",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
"volumeNumber": "48"
}
],
"keywords": [
"second-order logic",
"order logic",
"logic",
"concept",
"crucial difference",
"unranked tree automata",
"automata",
"expressive power",
"power",
"cases",
"differences",
"theory",
"weighted monadic second order logic",
"monadic second-order logic",
"unranked trees",
"trees",
"tree automata",
"MSO logic",
"same expressive power",
"semirings",
"weighted logic"
],
"name": "Weighted Logics for Unranked Tree Automata",
"pagination": "23-47",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1045410699"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s00224-009-9224-4"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s00224-009-9224-4",
"https://app.dimensions.ai/details/publication/pub.1045410699"
],
"sdDataset": "articles",
"sdDatePublished": "2022-05-20T07:25",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/article/article_494.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s00224-009-9224-4"
}
]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/s00224-009-9224-4'
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/s00224-009-9224-4'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-009-9224-4'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00224-009-9224-4'
This table displays all metadata directly associated to this object as RDF triples.
177 TRIPLES
22 PREDICATES
68 URIs
38 LITERALS
6 BLANK NODES