Weighted iterated linear control View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2018-06-15

AUTHORS

Zoltán Fülöp, Heiko Vogler

ABSTRACT

We combine three extensions of context-free grammars: (a) associating its nonterminals with storage configurations, (b) equipping its rules with weights, and (c) controlling its derivations. For a commutative semiring K, we introduce the class of weighted languages generated by K-weighted linear context-free grammars with storage S and with derivations controlled by (S, K)-recognizable weighted languages. The control on the derivations can be iterated in a natural way. We characterize the n-th iteration of the control in terms of the n-th iteration of the one-turn pushdown operator on the storage S of the control weighted language. Moreover, for each proper semiring we prove that iterating the control yields an infinite, strict hierarchy of classes of weighted languages. More... »

PAGES

447-469

References to SciGraph publications

  • 2016-02-26. A Weighted MSO Logic with Storage Behaviour and Its Büchi-Elgot-Trakhtenbrot Theorem in LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS
  • 2006. Hierarchies of Tree Series Transformations Revisited in DEVELOPMENTS IN LANGUAGE THEORY
  • 1986-12. Iterated linear control and iterated one-turn pushdowns in THEORY OF COMPUTING SYSTEMS
  • <error retrieving object. in <ERROR RETRIEVING OBJECT
  • 1968-06. Control sets on grammars in THEORY OF COMPUTING SYSTEMS
  • 1997. Grammars with Controlled Derivations in HANDBOOK OF FORMAL LANGUAGES
  • 2004. Input Reversals and Iterated Pushdown Automata: A New Characterization of Khabbaz Geometric Hierarchy of Languages in DEVELOPMENTS IN LANGUAGE THEORY
  • 1989. Regulated Rewriting in Formal Language Theory in NONE
  • 1978. Automata-Theoretic Aspects of Formal Power Series in NONE
  • 2013. The Chomsky-Schützenberger Theorem for Quantitative Context-Free Languages in DEVELOPMENTS IN LANGUAGE THEORY
  • 2015-09-09. A Chomsky-Schützenberger Theorem for Weighted Automata with Storage in ALGEBRAIC INFORMATICS
  • 1999. Semirings and their Applications in NONE
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00236-018-0325-x

    DOI

    http://dx.doi.org/10.1007/s00236-018-0325-x

    DIMENSIONS

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


    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/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/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/0803", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computer Software", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0804", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Data Format", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Institute of Informatics, University of Szeged, \u00c1rp\u00e1d t\u00e9r 2., 6720, Szeged, Hungary", 
              "id": "http://www.grid.ac/institutes/grid.9008.1", 
              "name": [
                "Institute of Informatics, University of Szeged, \u00c1rp\u00e1d t\u00e9r 2., 6720, Szeged, Hungary"
              ], 
              "type": "Organization"
            }, 
            "familyName": "F\u00fcl\u00f6p", 
            "givenName": "Zolt\u00e1n", 
            "id": "sg:person.014007607055.43", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014007607055.43"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Faculty of Computer Science, Technische Universit\u00e4t Dresden, 01062, Dresden, Germany", 
              "id": "http://www.grid.ac/institutes/grid.4488.0", 
              "name": [
                "Faculty 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-662-07675-0_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033948087", 
              "https://doi.org/10.1007/978-3-662-07675-0_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-38771-5_19", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030805197", 
              "https://doi.org/10.1007/978-3-642-38771-5_19"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01704910", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048170088", 
              "https://doi.org/10.1007/bf01704910"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-23021-4_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051520480", 
              "https://doi.org/10.1007/978-3-319-23021-4_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11779148_20", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004371477", 
              "https://doi.org/10.1007/11779148_20"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01692513", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037066141", 
              "https://doi.org/10.1007/bf01692513"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30550-7_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020831759", 
              "https://doi.org/10.1007/978-3-540-30550-7_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-30000-9_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014710697", 
              "https://doi.org/10.1007/978-3-319-30000-9_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-94-015-9333-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049390079", 
              "https://doi.org/10.1007/978-94-015-9333-5"
            ], 
            "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"
          }, 
          {
            "id": "sg:pub.10.1007/bf01695769", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033919759", 
              "https://doi.org/10.1007/bf01695769"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-74932-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1109710753", 
              "https://doi.org/10.1007/978-3-642-74932-2"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2018-06-15", 
        "datePublishedReg": "2018-06-15", 
        "description": "We combine three extensions of context-free grammars: (a) associating its nonterminals with storage configurations, (b)\u00a0equipping its rules with weights, and (c) controlling its derivations. For a commutative semiring K, we introduce the class of weighted languages generated by K-weighted linear context-free grammars with storage S and with derivations controlled by (S,\u00a0K)-recognizable weighted languages. The control on the derivations can be iterated in a natural way. We characterize the n-th iteration of the control in terms of the n-th iteration of the one-turn pushdown operator on the storage S of the control weighted language. Moreover, for each proper semiring we prove that iterating the control yields an infinite, strict hierarchy of classes of weighted languages.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00236-018-0325-x", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1133515", 
            "issn": [
              "0001-5903", 
              "1432-0525"
            ], 
            "name": "Acta Informatica", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "5", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "56"
          }
        ], 
        "keywords": [
          "storage S", 
          "linear control", 
          "natural way", 
          "derivation", 
          "iteration", 
          "context-free grammars", 
          "class", 
          "operators", 
          "semirings", 
          "linear context-free grammars", 
          "extension", 
          "language", 
          "grammar", 
          "control", 
          "terms", 
          "strict hierarchy", 
          "storage configuration", 
          "configuration", 
          "rules", 
          "hierarchy", 
          "nonterminals", 
          "way", 
          "weight"
        ], 
        "name": "Weighted iterated linear control", 
        "pagination": "447-469", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1104654919"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00236-018-0325-x"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00236-018-0325-x", 
          "https://app.dimensions.ai/details/publication/pub.1104654919"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-05-20T07:34", 
        "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_777.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00236-018-0325-x"
      }
    ]
     

    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/s00236-018-0325-x'

    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/s00236-018-0325-x'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00236-018-0325-x'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00236-018-0325-x'


     

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

    147 TRIPLES      22 PREDICATES      62 URIs      40 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00236-018-0325-x schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 anzsrc-for:0803
    4 anzsrc-for:0804
    5 schema:author Nec72e295ad1a4fc4b6b561a44bbcb13b
    6 schema:citation sg:pub.10.1007/11779148_20
    7 sg:pub.10.1007/978-1-4612-6264-0
    8 sg:pub.10.1007/978-3-319-23021-4_11
    9 sg:pub.10.1007/978-3-319-30000-9_10
    10 sg:pub.10.1007/978-3-540-30550-7_9
    11 sg:pub.10.1007/978-3-642-38771-5_19
    12 sg:pub.10.1007/978-3-642-74932-2
    13 sg:pub.10.1007/978-3-662-07675-0_3
    14 sg:pub.10.1007/978-94-015-9333-5
    15 sg:pub.10.1007/bf01692513
    16 sg:pub.10.1007/bf01695769
    17 sg:pub.10.1007/bf01704910
    18 schema:datePublished 2018-06-15
    19 schema:datePublishedReg 2018-06-15
    20 schema:description We combine three extensions of context-free grammars: (a) associating its nonterminals with storage configurations, (b) equipping its rules with weights, and (c) controlling its derivations. For a commutative semiring K, we introduce the class of weighted languages generated by K-weighted linear context-free grammars with storage S and with derivations controlled by (S, K)-recognizable weighted languages. The control on the derivations can be iterated in a natural way. We characterize the n-th iteration of the control in terms of the n-th iteration of the one-turn pushdown operator on the storage S of the control weighted language. Moreover, for each proper semiring we prove that iterating the control yields an infinite, strict hierarchy of classes of weighted languages.
    21 schema:genre article
    22 schema:inLanguage en
    23 schema:isAccessibleForFree false
    24 schema:isPartOf N24b4b11ee74b46809ba169390041c197
    25 N64fd8d80850b4116b7c6da6a593eccef
    26 sg:journal.1133515
    27 schema:keywords class
    28 configuration
    29 context-free grammars
    30 control
    31 derivation
    32 extension
    33 grammar
    34 hierarchy
    35 iteration
    36 language
    37 linear context-free grammars
    38 linear control
    39 natural way
    40 nonterminals
    41 operators
    42 rules
    43 semirings
    44 storage S
    45 storage configuration
    46 strict hierarchy
    47 terms
    48 way
    49 weight
    50 schema:name Weighted iterated linear control
    51 schema:pagination 447-469
    52 schema:productId N67162e0ac22643a28717ec532603fdc3
    53 N95c90bfa157b4434a4138842f528db46
    54 schema:sameAs https://app.dimensions.ai/details/publication/pub.1104654919
    55 https://doi.org/10.1007/s00236-018-0325-x
    56 schema:sdDatePublished 2022-05-20T07:34
    57 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    58 schema:sdPublisher N799eff6ff7b4426ab5efca6933f8b41c
    59 schema:url https://doi.org/10.1007/s00236-018-0325-x
    60 sgo:license sg:explorer/license/
    61 sgo:sdDataset articles
    62 rdf:type schema:ScholarlyArticle
    63 N24b4b11ee74b46809ba169390041c197 schema:volumeNumber 56
    64 rdf:type schema:PublicationVolume
    65 N2de00d01b4044bdaa9501b3d227acfa4 rdf:first sg:person.014562633673.93
    66 rdf:rest rdf:nil
    67 N64fd8d80850b4116b7c6da6a593eccef schema:issueNumber 5
    68 rdf:type schema:PublicationIssue
    69 N67162e0ac22643a28717ec532603fdc3 schema:name dimensions_id
    70 schema:value pub.1104654919
    71 rdf:type schema:PropertyValue
    72 N799eff6ff7b4426ab5efca6933f8b41c schema:name Springer Nature - SN SciGraph project
    73 rdf:type schema:Organization
    74 N95c90bfa157b4434a4138842f528db46 schema:name doi
    75 schema:value 10.1007/s00236-018-0325-x
    76 rdf:type schema:PropertyValue
    77 Nec72e295ad1a4fc4b6b561a44bbcb13b rdf:first sg:person.014007607055.43
    78 rdf:rest N2de00d01b4044bdaa9501b3d227acfa4
    79 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    80 schema:name Information and Computing Sciences
    81 rdf:type schema:DefinedTerm
    82 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    83 schema:name Computation Theory and Mathematics
    84 rdf:type schema:DefinedTerm
    85 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
    86 schema:name Computer Software
    87 rdf:type schema:DefinedTerm
    88 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
    89 schema:name Data Format
    90 rdf:type schema:DefinedTerm
    91 sg:journal.1133515 schema:issn 0001-5903
    92 1432-0525
    93 schema:name Acta Informatica
    94 schema:publisher Springer Nature
    95 rdf:type schema:Periodical
    96 sg:person.014007607055.43 schema:affiliation grid-institutes:grid.9008.1
    97 schema:familyName Fülöp
    98 schema:givenName Zoltán
    99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014007607055.43
    100 rdf:type schema:Person
    101 sg:person.014562633673.93 schema:affiliation grid-institutes:grid.4488.0
    102 schema:familyName Vogler
    103 schema:givenName Heiko
    104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014562633673.93
    105 rdf:type schema:Person
    106 sg:pub.10.1007/11779148_20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004371477
    107 https://doi.org/10.1007/11779148_20
    108 rdf:type schema:CreativeWork
    109 sg:pub.10.1007/978-1-4612-6264-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046944411
    110 https://doi.org/10.1007/978-1-4612-6264-0
    111 rdf:type schema:CreativeWork
    112 sg:pub.10.1007/978-3-319-23021-4_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051520480
    113 https://doi.org/10.1007/978-3-319-23021-4_11
    114 rdf:type schema:CreativeWork
    115 sg:pub.10.1007/978-3-319-30000-9_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014710697
    116 https://doi.org/10.1007/978-3-319-30000-9_10
    117 rdf:type schema:CreativeWork
    118 sg:pub.10.1007/978-3-540-30550-7_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020831759
    119 https://doi.org/10.1007/978-3-540-30550-7_9
    120 rdf:type schema:CreativeWork
    121 sg:pub.10.1007/978-3-642-38771-5_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030805197
    122 https://doi.org/10.1007/978-3-642-38771-5_19
    123 rdf:type schema:CreativeWork
    124 sg:pub.10.1007/978-3-642-74932-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1109710753
    125 https://doi.org/10.1007/978-3-642-74932-2
    126 rdf:type schema:CreativeWork
    127 sg:pub.10.1007/978-3-662-07675-0_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033948087
    128 https://doi.org/10.1007/978-3-662-07675-0_3
    129 rdf:type schema:CreativeWork
    130 sg:pub.10.1007/978-94-015-9333-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049390079
    131 https://doi.org/10.1007/978-94-015-9333-5
    132 rdf:type schema:CreativeWork
    133 sg:pub.10.1007/bf01692513 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037066141
    134 https://doi.org/10.1007/bf01692513
    135 rdf:type schema:CreativeWork
    136 sg:pub.10.1007/bf01695769 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033919759
    137 https://doi.org/10.1007/bf01695769
    138 rdf:type schema:CreativeWork
    139 sg:pub.10.1007/bf01704910 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048170088
    140 https://doi.org/10.1007/bf01704910
    141 rdf:type schema:CreativeWork
    142 grid-institutes:grid.4488.0 schema:alternateName Faculty of Computer Science, Technische Universität Dresden, 01062, Dresden, Germany
    143 schema:name Faculty of Computer Science, Technische Universität Dresden, 01062, Dresden, Germany
    144 rdf:type schema:Organization
    145 grid-institutes:grid.9008.1 schema:alternateName Institute of Informatics, University of Szeged, Árpád tér 2., 6720, Szeged, Hungary
    146 schema:name Institute of Informatics, University of Szeged, Árpád tér 2., 6720, Szeged, Hungary
    147 rdf:type schema:Organization
     




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


    ...