Ontology type: schema:Chapter Open Access: True
2008-01-01
AUTHORS ABSTRACTNested words, a model for recursive programs proposed by Alur and Madhusudan, have recently gained much interest. In this paper we introduce quantitative extensions and study nested word series which assign to nested words elements of a semiring. We show that regular nested word series coincide with series definable in weighted logics as introduced by Droste and Gastin. For this, we establish a connection between nested words and series-parallel-biposets. Applying our result, we obtain a characterization of algebraic formal power series in terms of weighted logics. This generalizes a result of Lautemann, Schwentick and Thérien on context-free languages. More... »
PAGES221-232
Automata, Languages and Programming
ISBN
978-3-540-70582-6
978-3-540-70583-3
http://scigraph.springernature.com/pub.10.1007/978-3-540-70583-3_19
DOIhttp://dx.doi.org/10.1007/978-3-540-70583-3_19
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1031990544
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/17",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Psychology and Cognitive Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1702",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Cognitive Sciences",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Institut f\u00fcr Informatik, Universit\u00e4t Leipzig, D-04009, Leipzig, Germany",
"id": "http://www.grid.ac/institutes/grid.9647.c",
"name": [
"Institut f\u00fcr Informatik, Universit\u00e4t Leipzig, D-04009, Leipzig, Germany"
],
"type": "Organization"
},
"familyName": "Mathissen",
"givenName": "Christian",
"id": "sg:person.014237551615.24",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014237551615.24"
],
"type": "Person"
}
],
"datePublished": "2008-01-01",
"datePublishedReg": "2008-01-01",
"description": "Nested words, a model for recursive programs proposed by Alur and Madhusudan, have recently gained much interest. In this paper we introduce quantitative extensions and study nested word series which assign to nested words elements of a semiring. We show that regular nested word series coincide with series definable in weighted logics as introduced by Droste and Gastin. For this, we establish a connection between nested words and series-parallel-biposets. Applying our result, we obtain a characterization of algebraic formal power series in terms of weighted logics. This generalizes a result of Lautemann, Schwentick and Th\u00e9rien on context-free languages.",
"editor": [
{
"familyName": "Aceto",
"givenName": "Luca",
"type": "Person"
},
{
"familyName": "Damg\u00e5rd",
"givenName": "Ivan",
"type": "Person"
},
{
"familyName": "Goldberg",
"givenName": "Leslie Ann",
"type": "Person"
},
{
"familyName": "Halld\u00f3rsson",
"givenName": "Magn\u00fas M.",
"type": "Person"
},
{
"familyName": "Ing\u00f3lfsd\u00f3ttir",
"givenName": "Anna",
"type": "Person"
},
{
"familyName": "Walukiewicz",
"givenName": "Igor",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-540-70583-3_19",
"inLanguage": "en",
"isAccessibleForFree": true,
"isPartOf": {
"isbn": [
"978-3-540-70582-6",
"978-3-540-70583-3"
],
"name": "Automata, Languages and Programming",
"type": "Book"
},
"keywords": [
"context-free languages",
"Nested Words",
"word series",
"word elements",
"words",
"logic",
"formal power series",
"language",
"Schwentick",
"Th\u00e9rien",
"Madhusudan",
"Droste",
"connection",
"recursive programs",
"Alur",
"interest",
"terms",
"program",
"paper",
"series",
"elements",
"semirings",
"quantitative extension",
"extension",
"coincide",
"model",
"results",
"power series",
"characterization",
"algebraic formal power series",
"series coincide",
"Gastin",
"weighted logic"
],
"name": "Weighted Logics for Nested Words and Algebraic Formal Power Series",
"pagination": "221-232",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1031990544"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-540-70583-3_19"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-540-70583-3_19",
"https://app.dimensions.ai/details/publication/pub.1031990544"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-06-01T22:34",
"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_382.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-540-70583-3_19"
}
]
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-540-70583-3_19'
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-540-70583-3_19'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-70583-3_19'
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-540-70583-3_19'
This table displays all metadata directly associated to this object as RDF triples.
118 TRIPLES
23 PREDICATES
58 URIs
51 LITERALS
7 BLANK NODES