Iterated linear control and iterated one-turn pushdowns View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1986-12

AUTHORS

Heiko Vogler

ABSTRACT

For a classℒ of languages, anℒ-controlled linear grammarK consists of a linear context-free grammarG and a control languageH inℒ, where the terminals ofH are interpreted as the labels of rules ofG. The language generated byK is obtained by derivations ofG such that the corresponding strings of labels of the rules applied are control strings inH. The control of linear grammars can be iterated by starting withℒ and by taking the result of thekth step as class of control languages for the (k + 1)st step. The language class obtained by thekth step is denoted by CTRLk(ℒ). Denote byℒ(S) the language class accepted by nondeterministic one-wayS automata, whereS is a storage type. We prove that for anyS, CTRLk(ℒ(S)) = ℒ(P1tk(S)), whereP1tk(S) is the storage type the configurations of which consist ofk-iterated one-turn pushdowns ofS-configurations. We establish a strong connection between iterated linear control and iterated one-turn pushdowns. In particular, we characterize CTRLk(ℒCF), where ℒCF is the class of context-free languages, by iterated one-turn pushdown automata in which the innermost pushdown is unrestricted. More... »

PAGES

117-133

References to SciGraph publications

  • 1982. An automata-theoretic characterization of the OI-hierarchy in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 1974. Notes on pre-set pushdown automata in L SYSTEMS
  • 1986. The ETOL Hierarchy is in the oi Hierarchy in THE BOOK OF L
  • 1968-06. Control sets on grammars in THEORY OF COMPUTING SYSTEMS
  • 1975. An algebraic formulation of the Chomsky hierarchy in CATEGORY THEORY APPLIED TO COMPUTATION AND CONTROL
  • 1972-12. Proof of correctness of data representations in ACTA INFORMATICA
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/bf01704910

    DOI

    http://dx.doi.org/10.1007/bf01704910

    DIMENSIONS

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


    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/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "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/0102", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Applied Mathematics", 
            "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/0805", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Distributed Computing", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Leiden, P.O. Box 9512, 2300 RA, Leiden, The Netherlands", 
              "id": "http://www.grid.ac/institutes/grid.5132.5", 
              "name": [
                "University of Leiden, P.O. Box 9512, 2300 RA, Leiden, The Netherlands"
              ], 
              "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/bf01692513", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037066141", 
              "https://doi.org/10.1007/bf01692513"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00289507", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028933316", 
              "https://doi.org/10.1007/bf00289507"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-95486-3_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011438867", 
              "https://doi.org/10.1007/978-3-642-95486-3_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-07142-3_84", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024578216", 
              "https://doi.org/10.1007/3-540-07142-3_84"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-06867-8_14", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035951250", 
              "https://doi.org/10.1007/3-540-06867-8_14"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0012764", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029171011", 
              "https://doi.org/10.1007/bfb0012764"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1986-12", 
        "datePublishedReg": "1986-12-01", 
        "description": "For a class\u2112 of languages, an\u2112-controlled linear grammarK consists of a linear context-free grammarG and a control languageH in\u2112, where the terminals ofH are interpreted as the labels of rules ofG. The language generated byK is obtained by derivations ofG such that the corresponding strings of labels of the rules applied are control strings inH. The control of linear grammars can be iterated by starting with\u2112 and by taking the result of thekth step as class of control languages for the (k + 1)st step. The language class obtained by thekth step is denoted by CTRLk(\u2112). Denote by\u2112(S) the language class accepted by nondeterministic one-wayS automata, whereS is a storage type. We prove that for anyS, CTRLk(\u2112(S)) = \u2112(P1tk(S)), whereP1tk(S) is the storage type the configurations of which consist ofk-iterated one-turn pushdowns ofS-configurations. We establish a strong connection between iterated linear control and iterated one-turn pushdowns. In particular, we characterize CTRLk(\u2112CF), where \u2112CF is the class of context-free languages, by iterated one-turn pushdown automata in which the innermost pushdown is unrestricted.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/bf01704910", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1052098", 
            "issn": [
              "1432-4350", 
              "1433-0490"
            ], 
            "name": "Theory of Computing Systems", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "19"
          }
        ], 
        "keywords": [
          "language classes", 
          "context-free languages", 
          "language", 
          "linear grammars", 
          "one-way automata", 
          "control language", 
          "pushdown automata", 
          "control strings", 
          "strong connection", 
          "grammar", 
          "pushdown", 
          "corresponding strings", 
          "automata", 
          "class", 
          "labels", 
          "rules", 
          "connection", 
          "strings", 
          "denotes", 
          "types", 
          "storage types", 
          "step", 
          "configuration", 
          "results", 
          "control", 
          "ofH", 
          "ofG", 
          "linear control", 
          "BYK", 
          "whereS", 
          "ofK", 
          "one-turn"
        ], 
        "name": "Iterated linear control and iterated one-turn pushdowns", 
        "pagination": "117-133", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1048170088"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf01704910"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf01704910", 
          "https://app.dimensions.ai/details/publication/pub.1048170088"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-05-20T07:17", 
        "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_181.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/bf01704910"
      }
    ]
     

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

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

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf01704910'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf01704910'


     

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

    126 TRIPLES      22 PREDICATES      67 URIs      50 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf01704910 schema:about anzsrc-for:01
    2 anzsrc-for:0102
    3 anzsrc-for:08
    4 anzsrc-for:0802
    5 anzsrc-for:0805
    6 schema:author N7d7503933ce8431c81835dcad6e26d48
    7 schema:citation sg:pub.10.1007/3-540-06867-8_14
    8 sg:pub.10.1007/3-540-07142-3_84
    9 sg:pub.10.1007/978-3-642-95486-3_8
    10 sg:pub.10.1007/bf00289507
    11 sg:pub.10.1007/bf01692513
    12 sg:pub.10.1007/bfb0012764
    13 schema:datePublished 1986-12
    14 schema:datePublishedReg 1986-12-01
    15 schema:description For a classℒ of languages, anℒ-controlled linear grammarK consists of a linear context-free grammarG and a control languageH inℒ, where the terminals ofH are interpreted as the labels of rules ofG. The language generated byK is obtained by derivations ofG such that the corresponding strings of labels of the rules applied are control strings inH. The control of linear grammars can be iterated by starting withℒ and by taking the result of thekth step as class of control languages for the (k + 1)st step. The language class obtained by thekth step is denoted by CTRLk(ℒ). Denote byℒ(S) the language class accepted by nondeterministic one-wayS automata, whereS is a storage type. We prove that for anyS, CTRLk(ℒ(S)) = ℒ(P1tk(S)), whereP1tk(S) is the storage type the configurations of which consist ofk-iterated one-turn pushdowns ofS-configurations. We establish a strong connection between iterated linear control and iterated one-turn pushdowns. In particular, we characterize CTRLk(ℒCF), where ℒCF is the class of context-free languages, by iterated one-turn pushdown automata in which the innermost pushdown is unrestricted.
    16 schema:genre article
    17 schema:inLanguage en
    18 schema:isAccessibleForFree false
    19 schema:isPartOf N9b14a4b669b24736a49c5db823c70d30
    20 Ned56ac91b282460f82c2869bad2d8d8a
    21 sg:journal.1052098
    22 schema:keywords BYK
    23 automata
    24 class
    25 configuration
    26 connection
    27 context-free languages
    28 control
    29 control language
    30 control strings
    31 corresponding strings
    32 denotes
    33 grammar
    34 labels
    35 language
    36 language classes
    37 linear control
    38 linear grammars
    39 ofG
    40 ofH
    41 ofK
    42 one-turn
    43 one-way automata
    44 pushdown
    45 pushdown automata
    46 results
    47 rules
    48 step
    49 storage types
    50 strings
    51 strong connection
    52 types
    53 whereS
    54 schema:name Iterated linear control and iterated one-turn pushdowns
    55 schema:pagination 117-133
    56 schema:productId N0f20a522cee44e8ab8c76d7dfc5e0e2e
    57 N64d579743be24fa395284d4538991253
    58 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048170088
    59 https://doi.org/10.1007/bf01704910
    60 schema:sdDatePublished 2022-05-20T07:17
    61 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    62 schema:sdPublisher N54f30f6e045d4ec3b69aad96edbbecfd
    63 schema:url https://doi.org/10.1007/bf01704910
    64 sgo:license sg:explorer/license/
    65 sgo:sdDataset articles
    66 rdf:type schema:ScholarlyArticle
    67 N0f20a522cee44e8ab8c76d7dfc5e0e2e schema:name doi
    68 schema:value 10.1007/bf01704910
    69 rdf:type schema:PropertyValue
    70 N54f30f6e045d4ec3b69aad96edbbecfd schema:name Springer Nature - SN SciGraph project
    71 rdf:type schema:Organization
    72 N64d579743be24fa395284d4538991253 schema:name dimensions_id
    73 schema:value pub.1048170088
    74 rdf:type schema:PropertyValue
    75 N7d7503933ce8431c81835dcad6e26d48 rdf:first sg:person.014562633673.93
    76 rdf:rest rdf:nil
    77 N9b14a4b669b24736a49c5db823c70d30 schema:volumeNumber 19
    78 rdf:type schema:PublicationVolume
    79 Ned56ac91b282460f82c2869bad2d8d8a schema:issueNumber 1
    80 rdf:type schema:PublicationIssue
    81 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    82 schema:name Mathematical Sciences
    83 rdf:type schema:DefinedTerm
    84 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
    85 schema:name Applied Mathematics
    86 rdf:type schema:DefinedTerm
    87 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    88 schema:name Information and Computing Sciences
    89 rdf:type schema:DefinedTerm
    90 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    91 schema:name Computation Theory and Mathematics
    92 rdf:type schema:DefinedTerm
    93 anzsrc-for:0805 schema:inDefinedTermSet anzsrc-for:
    94 schema:name Distributed Computing
    95 rdf:type schema:DefinedTerm
    96 sg:journal.1052098 schema:issn 1432-4350
    97 1433-0490
    98 schema:name Theory of Computing Systems
    99 schema:publisher Springer Nature
    100 rdf:type schema:Periodical
    101 sg:person.014562633673.93 schema:affiliation grid-institutes:grid.5132.5
    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/3-540-06867-8_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035951250
    107 https://doi.org/10.1007/3-540-06867-8_14
    108 rdf:type schema:CreativeWork
    109 sg:pub.10.1007/3-540-07142-3_84 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024578216
    110 https://doi.org/10.1007/3-540-07142-3_84
    111 rdf:type schema:CreativeWork
    112 sg:pub.10.1007/978-3-642-95486-3_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011438867
    113 https://doi.org/10.1007/978-3-642-95486-3_8
    114 rdf:type schema:CreativeWork
    115 sg:pub.10.1007/bf00289507 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028933316
    116 https://doi.org/10.1007/bf00289507
    117 rdf:type schema:CreativeWork
    118 sg:pub.10.1007/bf01692513 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037066141
    119 https://doi.org/10.1007/bf01692513
    120 rdf:type schema:CreativeWork
    121 sg:pub.10.1007/bfb0012764 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029171011
    122 https://doi.org/10.1007/bfb0012764
    123 rdf:type schema:CreativeWork
    124 grid-institutes:grid.5132.5 schema:alternateName University of Leiden, P.O. Box 9512, 2300 RA, Leiden, The Netherlands
    125 schema:name University of Leiden, P.O. Box 9512, 2300 RA, Leiden, The Netherlands
    126 rdf:type schema:Organization
     




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


    ...