The Chomsky-Schützenberger Theorem for Quantitative Context-Free Languages View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2013

AUTHORS

Manfred Droste , Heiko Vogler

ABSTRACT

Weighted automata model quantitative aspects of systems like the consumption of resources during executions. Traditionally, the weights are assumed to form the algebraic structure of a semiring, but recently also other weight computations like average have been considered. Here, we investigate quantitative context-free languages over very general weight structures incorporating all semirings, average computations, lattices. In our main result, we derive the Chomsky-Schützenberger Theorem for such quantitative context-free languages, showing that each arises as the image of the intersection of a Dyck language and a recognizable language under a suitable morphism. Moreover, we show that quantitative context-free languages are expressively equivalent to a model of weighted pushdown automata. This generalizes results previously known only for semirings. More... »

PAGES

203-214

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-38771-5_19

DOI

http://dx.doi.org/10.1007/978-3-642-38771-5_19

DIMENSIONS

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


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/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": "Institute of Computer Science, Leipzig University, D-04109, Leipzig, Germany", 
          "id": "http://www.grid.ac/institutes/grid.9647.c", 
          "name": [
            "Institute of Computer Science, Leipzig University, D-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, D-01062, Dresden, Germany", 
          "id": "http://www.grid.ac/institutes/grid.4488.0", 
          "name": [
            "Department of Computer Science, Technische Universit\u00e4t Dresden, D-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"
      }
    ], 
    "datePublished": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "Weighted automata model quantitative aspects of systems like the consumption of resources during executions. Traditionally, the weights are assumed to form the algebraic structure of a semiring, but recently also other weight computations like average have been considered. Here, we investigate quantitative context-free languages over very general weight structures incorporating all semirings, average computations, lattices. In our main result, we derive the Chomsky-Sch\u00fctzenberger Theorem for such quantitative context-free languages, showing that each arises as the image of the intersection of a Dyck language and a recognizable language under a suitable morphism. Moreover, we show that quantitative context-free languages are expressively equivalent to a model of weighted pushdown automata. This generalizes results previously known only for semirings.", 
    "editor": [
      {
        "familyName": "B\u00e9al", 
        "givenName": "Marie-Pierre", 
        "type": "Person"
      }, 
      {
        "familyName": "Carton", 
        "givenName": "Olivier", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-38771-5_19", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-38770-8", 
        "978-3-642-38771-5"
      ], 
      "name": "Developments in Language Theory", 
      "type": "Book"
    }, 
    "keywords": [
      "context-free languages", 
      "Chomsky-Sch\u00fctzenberger theorem", 
      "Dyck languages", 
      "recognizable languages", 
      "language", 
      "suitable morphisms", 
      "pushdown automata", 
      "average computation", 
      "intersection", 
      "consumption of resources", 
      "aspects", 
      "semirings", 
      "weight computation", 
      "images", 
      "automata", 
      "quantitative aspects", 
      "resources", 
      "computation", 
      "algebraic structure", 
      "execution", 
      "consumption", 
      "morphisms", 
      "structure", 
      "system", 
      "model", 
      "main results", 
      "theorem", 
      "results", 
      "weight structures", 
      "weight", 
      "lattice"
    ], 
    "name": "The Chomsky-Sch\u00fctzenberger Theorem for Quantitative Context-Free Languages", 
    "pagination": "203-214", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1030805197"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-38771-5_19"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-38771-5_19", 
      "https://app.dimensions.ai/details/publication/pub.1030805197"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:46", 
    "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/chapter/chapter_349.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-38771-5_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-642-38771-5_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-642-38771-5_19'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-38771-5_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-642-38771-5_19'


 

This table displays all metadata directly associated to this object as RDF triples.

106 TRIPLES      23 PREDICATES      57 URIs      50 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-38771-5_19 schema:about anzsrc-for:20
2 anzsrc-for:2004
3 schema:author Na34fcdeff744421a9eccf117f9f5c754
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema:description Weighted automata model quantitative aspects of systems like the consumption of resources during executions. Traditionally, the weights are assumed to form the algebraic structure of a semiring, but recently also other weight computations like average have been considered. Here, we investigate quantitative context-free languages over very general weight structures incorporating all semirings, average computations, lattices. In our main result, we derive the Chomsky-Schützenberger Theorem for such quantitative context-free languages, showing that each arises as the image of the intersection of a Dyck language and a recognizable language under a suitable morphism. Moreover, we show that quantitative context-free languages are expressively equivalent to a model of weighted pushdown automata. This generalizes results previously known only for semirings.
7 schema:editor Nbee0682135264368949436d74496d8b8
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N191168bd501a4db5b902dee4df0c63bb
12 schema:keywords Chomsky-Schützenberger theorem
13 Dyck languages
14 algebraic structure
15 aspects
16 automata
17 average computation
18 computation
19 consumption
20 consumption of resources
21 context-free languages
22 execution
23 images
24 intersection
25 language
26 lattice
27 main results
28 model
29 morphisms
30 pushdown automata
31 quantitative aspects
32 recognizable languages
33 resources
34 results
35 semirings
36 structure
37 suitable morphisms
38 system
39 theorem
40 weight
41 weight computation
42 weight structures
43 schema:name The Chomsky-Schützenberger Theorem for Quantitative Context-Free Languages
44 schema:pagination 203-214
45 schema:productId Nbef83fd59ba844a8ac90a95a25402ee2
46 Nc6f154531ce84258b2ddf2b866112b4d
47 schema:publisher N5740319a51ba492688d1aa94444a21c1
48 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030805197
49 https://doi.org/10.1007/978-3-642-38771-5_19
50 schema:sdDatePublished 2022-05-20T07:46
51 schema:sdLicense https://scigraph.springernature.com/explorer/license/
52 schema:sdPublisher N5d63e1965cfa4b32909dfe5781455738
53 schema:url https://doi.org/10.1007/978-3-642-38771-5_19
54 sgo:license sg:explorer/license/
55 sgo:sdDataset chapters
56 rdf:type schema:Chapter
57 N01287ce2f1404c0f9e305dde24e6caa3 schema:familyName Carton
58 schema:givenName Olivier
59 rdf:type schema:Person
60 N191168bd501a4db5b902dee4df0c63bb schema:isbn 978-3-642-38770-8
61 978-3-642-38771-5
62 schema:name Developments in Language Theory
63 rdf:type schema:Book
64 N5740319a51ba492688d1aa94444a21c1 schema:name Springer Nature
65 rdf:type schema:Organisation
66 N5d63e1965cfa4b32909dfe5781455738 schema:name Springer Nature - SN SciGraph project
67 rdf:type schema:Organization
68 N5ef38d06dec74a72b1685326f9ffcda2 schema:familyName Béal
69 schema:givenName Marie-Pierre
70 rdf:type schema:Person
71 Na34fcdeff744421a9eccf117f9f5c754 rdf:first sg:person.010545141652.14
72 rdf:rest Nea713598274d40388c0d40ee821ac578
73 Nbee0682135264368949436d74496d8b8 rdf:first N5ef38d06dec74a72b1685326f9ffcda2
74 rdf:rest Nd2a0bb12363f4daea80ae3604c3dab8f
75 Nbef83fd59ba844a8ac90a95a25402ee2 schema:name doi
76 schema:value 10.1007/978-3-642-38771-5_19
77 rdf:type schema:PropertyValue
78 Nc6f154531ce84258b2ddf2b866112b4d schema:name dimensions_id
79 schema:value pub.1030805197
80 rdf:type schema:PropertyValue
81 Nd2a0bb12363f4daea80ae3604c3dab8f rdf:first N01287ce2f1404c0f9e305dde24e6caa3
82 rdf:rest rdf:nil
83 Nea713598274d40388c0d40ee821ac578 rdf:first sg:person.014562633673.93
84 rdf:rest rdf:nil
85 anzsrc-for:20 schema:inDefinedTermSet anzsrc-for:
86 schema:name Language, Communication and Culture
87 rdf:type schema:DefinedTerm
88 anzsrc-for:2004 schema:inDefinedTermSet anzsrc-for:
89 schema:name Linguistics
90 rdf:type schema:DefinedTerm
91 sg:person.010545141652.14 schema:affiliation grid-institutes:grid.9647.c
92 schema:familyName Droste
93 schema:givenName Manfred
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010545141652.14
95 rdf:type schema:Person
96 sg:person.014562633673.93 schema:affiliation grid-institutes:grid.4488.0
97 schema:familyName Vogler
98 schema:givenName Heiko
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014562633673.93
100 rdf:type schema:Person
101 grid-institutes:grid.4488.0 schema:alternateName Department of Computer Science, Technische Universität Dresden, D-01062, Dresden, Germany
102 schema:name Department of Computer Science, Technische Universität Dresden, D-01062, Dresden, Germany
103 rdf:type schema:Organization
104 grid-institutes:grid.9647.c schema:alternateName Institute of Computer Science, Leipzig University, D-04109, Leipzig, Germany
105 schema:name Institute of Computer Science, Leipzig University, D-04109, Leipzig, Germany
106 rdf:type schema:Organization
 




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


...