Weighted Logics for Nested Words and Algebraic Formal Power Series View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2008-01-01

AUTHORS

Christian Mathissen

ABSTRACT

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érien on context-free languages. More... »

PAGES

221-232

Book

TITLE

Automata, Languages and Programming

ISBN

978-3-540-70582-6
978-3-540-70583-3

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-70583-3_19

DOI

http://dx.doi.org/10.1007/978-3-540-70583-3_19

DIMENSIONS

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


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/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

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

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-70583-3_19 schema:about anzsrc-for:17
2 anzsrc-for:1702
3 schema:author Nf91bd879ca8d4563941ab9699f7cc694
4 schema:datePublished 2008-01-01
5 schema:datePublishedReg 2008-01-01
6 schema: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érien on context-free languages.
7 schema:editor N154dc5e9e1bf460e9e50526741b58a81
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nad4e17fb19614b96b1349c73ad049092
12 schema:keywords Alur
13 Droste
14 Gastin
15 Madhusudan
16 Nested Words
17 Schwentick
18 Thérien
19 algebraic formal power series
20 characterization
21 coincide
22 connection
23 context-free languages
24 elements
25 extension
26 formal power series
27 interest
28 language
29 logic
30 model
31 paper
32 power series
33 program
34 quantitative extension
35 recursive programs
36 results
37 semirings
38 series
39 series coincide
40 terms
41 weighted logic
42 word elements
43 word series
44 words
45 schema:name Weighted Logics for Nested Words and Algebraic Formal Power Series
46 schema:pagination 221-232
47 schema:productId N3d18f456b4ad4c02a8ebab874caa972d
48 N4785d55305ea439bb2297c7488764a41
49 schema:publisher Nfaa8e749c811419a9c2b2340bc396ccf
50 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031990544
51 https://doi.org/10.1007/978-3-540-70583-3_19
52 schema:sdDatePublished 2022-06-01T22:34
53 schema:sdLicense https://scigraph.springernature.com/explorer/license/
54 schema:sdPublisher N5e33d490698342d888687aa2a3f583e4
55 schema:url https://doi.org/10.1007/978-3-540-70583-3_19
56 sgo:license sg:explorer/license/
57 sgo:sdDataset chapters
58 rdf:type schema:Chapter
59 N154dc5e9e1bf460e9e50526741b58a81 rdf:first N9ef37ab71aa74e72bb7dfd1545434467
60 rdf:rest N16ab6532abe6475f92acf6b8cf9b1197
61 N16ab6532abe6475f92acf6b8cf9b1197 rdf:first Nf58782d942954f4385e17be123779d3e
62 rdf:rest N4318948d8e2a4015abab9fce2fd41476
63 N2522fba1641a46fe8af0283273a89a44 rdf:first N8008b7d86a2545bba7bc9f9327ef3d73
64 rdf:rest N9cb3b3141d7c4a5bb75ae7b7cb920fa0
65 N3d18f456b4ad4c02a8ebab874caa972d schema:name doi
66 schema:value 10.1007/978-3-540-70583-3_19
67 rdf:type schema:PropertyValue
68 N4318948d8e2a4015abab9fce2fd41476 rdf:first Na4bf769315c049b9ae6457499d94e18d
69 rdf:rest N2522fba1641a46fe8af0283273a89a44
70 N4785d55305ea439bb2297c7488764a41 schema:name dimensions_id
71 schema:value pub.1031990544
72 rdf:type schema:PropertyValue
73 N5cc25fe24c234b78911677ca18f63361 schema:familyName Ingólfsdóttir
74 schema:givenName Anna
75 rdf:type schema:Person
76 N5e33d490698342d888687aa2a3f583e4 schema:name Springer Nature - SN SciGraph project
77 rdf:type schema:Organization
78 N8008b7d86a2545bba7bc9f9327ef3d73 schema:familyName Halldórsson
79 schema:givenName Magnús M.
80 rdf:type schema:Person
81 N9cb3b3141d7c4a5bb75ae7b7cb920fa0 rdf:first N5cc25fe24c234b78911677ca18f63361
82 rdf:rest Nb239b329ddd74e72a67be484bb70cfe0
83 N9ef37ab71aa74e72bb7dfd1545434467 schema:familyName Aceto
84 schema:givenName Luca
85 rdf:type schema:Person
86 Na4bf769315c049b9ae6457499d94e18d schema:familyName Goldberg
87 schema:givenName Leslie Ann
88 rdf:type schema:Person
89 Nad4e17fb19614b96b1349c73ad049092 schema:isbn 978-3-540-70582-6
90 978-3-540-70583-3
91 schema:name Automata, Languages and Programming
92 rdf:type schema:Book
93 Nb239b329ddd74e72a67be484bb70cfe0 rdf:first Ndda1fadb989c48ed9975326a1592168b
94 rdf:rest rdf:nil
95 Ndda1fadb989c48ed9975326a1592168b schema:familyName Walukiewicz
96 schema:givenName Igor
97 rdf:type schema:Person
98 Nf58782d942954f4385e17be123779d3e schema:familyName Damgård
99 schema:givenName Ivan
100 rdf:type schema:Person
101 Nf91bd879ca8d4563941ab9699f7cc694 rdf:first sg:person.014237551615.24
102 rdf:rest rdf:nil
103 Nfaa8e749c811419a9c2b2340bc396ccf schema:name Springer Nature
104 rdf:type schema:Organisation
105 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
106 schema:name Psychology and Cognitive Sciences
107 rdf:type schema:DefinedTerm
108 anzsrc-for:1702 schema:inDefinedTermSet anzsrc-for:
109 schema:name Cognitive Sciences
110 rdf:type schema:DefinedTerm
111 sg:person.014237551615.24 schema:affiliation grid-institutes:grid.9647.c
112 schema:familyName Mathissen
113 schema:givenName Christian
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014237551615.24
115 rdf:type schema:Person
116 grid-institutes:grid.9647.c schema:alternateName Institut für Informatik, Universität Leipzig, D-04009, Leipzig, Germany
117 schema:name Institut für Informatik, Universität Leipzig, D-04009, Leipzig, Germany
118 rdf:type schema:Organization
 




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


...