A Weighted MSO Logic with Storage Behaviour and Its Büchi-Elgot-Trakhtenbrot Theorem View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2016-02-26

AUTHORS

Heiko Vogler , Manfred Droste , Luisa Herrmann

ABSTRACT

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ü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... »

PAGES

127-139

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-30000-9_10

DOI

http://dx.doi.org/10.1007/978-3-319-30000-9_10

DIMENSIONS

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


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

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

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-30000-9_10 schema:about anzsrc-for:15
2 anzsrc-for:1502
3 schema:author N47a5e6ae1d9c4cc0ac3879a2e7e35ed6
4 schema:datePublished 2016-02-26
5 schema:datePublishedReg 2016-02-26
6 schema: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ü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.
7 schema:editor N8f76c397072f4bff886fc65bc0a16392
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N7df741e8a46340178720972b18d2af82
12 schema:keywords Büchi-Elgot
13 MSO logic
14 Trakhtenbrot Theorem
15 automata
16 behavior
17 choice
18 computation
19 cost
20 elements
21 existential quantification
22 finite words
23 formula
24 infimum
25 language
26 lattice
27 logic
28 monoids
29 problem
30 pushdown languages
31 quantification
32 satisfiability problem
33 semirings
34 storage
35 storage behavior
36 storage types
37 structure
38 theorem
39 types
40 valuation monoids
41 weight structures
42 words
43 schema:name A Weighted MSO Logic with Storage Behaviour and Its Büchi-Elgot-Trakhtenbrot Theorem
44 schema:pagination 127-139
45 schema:productId N67e7fc2eee4c41c7842be9bc0f90d3c9
46 N6ae6e1999b6741f29e82f703d9768b0f
47 schema:publisher N28aea50d6f3649adbe53b00850c2d100
48 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014710697
49 https://doi.org/10.1007/978-3-319-30000-9_10
50 schema:sdDatePublished 2022-05-10T10:47
51 schema:sdLicense https://scigraph.springernature.com/explorer/license/
52 schema:sdPublisher N6e7baad610604ec2896e128f7697be0e
53 schema:url https://doi.org/10.1007/978-3-319-30000-9_10
54 sgo:license sg:explorer/license/
55 sgo:sdDataset chapters
56 rdf:type schema:Chapter
57 N0bee7359b72e427895e25c0123583ef8 schema:familyName Truthe
58 schema:givenName Bianca
59 rdf:type schema:Person
60 N189c00414637456fa755643b5e4a5b24 rdf:first N7bd34f433b064ec88af313ee9fa4f51d
61 rdf:rest Nbf893823a73249fd8b6239b7885f02dd
62 N28aea50d6f3649adbe53b00850c2d100 schema:name Springer Nature
63 rdf:type schema:Organisation
64 N2967ab914da8407fb27d09f4aeb0c9db schema:familyName Martín-Vide
65 schema:givenName Carlos
66 rdf:type schema:Person
67 N403969a091eb43a08c8c17f9858f5709 rdf:first sg:person.010752400543.10
68 rdf:rest rdf:nil
69 N47a5e6ae1d9c4cc0ac3879a2e7e35ed6 rdf:first sg:person.014562633673.93
70 rdf:rest Nd74c5a5366e644d683e02764586ea07f
71 N67e7fc2eee4c41c7842be9bc0f90d3c9 schema:name doi
72 schema:value 10.1007/978-3-319-30000-9_10
73 rdf:type schema:PropertyValue
74 N6ae6e1999b6741f29e82f703d9768b0f schema:name dimensions_id
75 schema:value pub.1014710697
76 rdf:type schema:PropertyValue
77 N6e7baad610604ec2896e128f7697be0e schema:name Springer Nature - SN SciGraph project
78 rdf:type schema:Organization
79 N7bd34f433b064ec88af313ee9fa4f51d schema:familyName Janoušek
80 schema:givenName Jan
81 rdf:type schema:Person
82 N7df741e8a46340178720972b18d2af82 schema:isbn 978-3-319-29999-0
83 978-3-319-30000-9
84 schema:name Language and Automata Theory and Applications
85 rdf:type schema:Book
86 N8c5e3ef39e6241b1af86c5ebc5607bfa schema:familyName Dediu
87 schema:givenName Adrian-Horia
88 rdf:type schema:Person
89 N8f76c397072f4bff886fc65bc0a16392 rdf:first N8c5e3ef39e6241b1af86c5ebc5607bfa
90 rdf:rest N189c00414637456fa755643b5e4a5b24
91 Nbbac2302bc3647879c0374d8878509ad rdf:first N0bee7359b72e427895e25c0123583ef8
92 rdf:rest rdf:nil
93 Nbf893823a73249fd8b6239b7885f02dd rdf:first N2967ab914da8407fb27d09f4aeb0c9db
94 rdf:rest Nbbac2302bc3647879c0374d8878509ad
95 Nd74c5a5366e644d683e02764586ea07f rdf:first sg:person.010545141652.14
96 rdf:rest N403969a091eb43a08c8c17f9858f5709
97 anzsrc-for:15 schema:inDefinedTermSet anzsrc-for:
98 schema:name Commerce, Management, Tourism and Services
99 rdf:type schema:DefinedTerm
100 anzsrc-for:1502 schema:inDefinedTermSet anzsrc-for:
101 schema:name Banking, Finance and Investment
102 rdf:type schema:DefinedTerm
103 sg:person.010545141652.14 schema:affiliation grid-institutes:grid.9647.c
104 schema:familyName Droste
105 schema:givenName Manfred
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010545141652.14
107 rdf:type schema:Person
108 sg:person.010752400543.10 schema:affiliation grid-institutes:grid.4488.0
109 schema:familyName Herrmann
110 schema:givenName Luisa
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010752400543.10
112 rdf:type schema:Person
113 sg:person.014562633673.93 schema:affiliation grid-institutes:grid.4488.0
114 schema:familyName Vogler
115 schema:givenName Heiko
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014562633673.93
117 rdf:type schema:Person
118 grid-institutes:grid.4488.0 schema:alternateName Faculty of Computer Science, Technische Universität Dresden, Dresden, Germany
119 schema:name Faculty of Computer Science, Technische Universität Dresden, Dresden, Germany
120 rdf:type schema:Organization
121 grid-institutes:grid.9647.c schema:alternateName Institut Für Informatik, Universität Leipzig, Leipzig, Germany
122 schema:name Institut Für Informatik, Universität Leipzig, Leipzig, Germany
123 rdf:type schema:Organization
 




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


...