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


Ontology type: schema:Chapter     


Chapter Info

DATE

1985

AUTHORS

Heiko Vogler

ABSTRACT

For a class of languages £, an £-controlled linear grammar K consists of a linear context-free grammar G and a control language H in £, where the terminals of H are interpreted as the labels of rules of G. The language generated by K is obtained by derivations of G such that the corresponding words of applied rules are control strings in H. The control of linear grammars can be iterated by starting with £ and by taking the result of the k-th step as class of control languages for the (k+1)-st step. The language class obtained by the k-th step is denoted by CTRLk (£). Denote by £(S) the language class accepted by nondeterministic one-way S automata, where S is a storage type. We prove that for any S, CTRLk(£(S))=£(Pltk (S)), where Pltk(S) is the storage type of which the configurations consist of k-iterated one-turn pushdowns of S-configurations, i.e., one-turn pushdowns of one-turn pushdowns of … of one-turn pushdowns of S-configurations (k times). Thereby we prove a strong connection between iterated linear control and iterated one-turn pushdowns. In particular, we characterize the members of the geometric language hierarchy (where £(S) is the class of context-free languages) by iterated one-turn pushdown automata in which the innermost pushdown is unrestricted. More... »

PAGES

474-484

Book

TITLE

Fundamentals of Computation Theory

ISBN

3-540-15689-5

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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": "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"
      }
    ], 
    "datePublished": "1985", 
    "datePublishedReg": "1985-01-01", 
    "description": "For a class of languages \u00a3, an \u00a3-controlled linear grammar K consists of a linear context-free grammar G and a control language H in \u00a3, where the terminals of H are interpreted as the labels of rules of G. The language generated by K is obtained by derivations of G such that the corresponding words of applied rules are control strings in H. The control of linear grammars can be iterated by starting with \u00a3 and by taking the result of the k-th step as class of control languages for the (k+1)-st step. The language class obtained by the k-th step is denoted by CTRLk (\u00a3). Denote by \u00a3(S) the language class accepted by nondeterministic one-way S automata, where S is a storage type. We prove that for any S, CTRLk(\u00a3(S))=\u00a3(Pltk (S)), where Pltk(S) is the storage type of which the configurations consist of k-iterated one-turn pushdowns of S-configurations, i.e., one-turn pushdowns of one-turn pushdowns of \u2026 of one-turn pushdowns of S-configurations (k times). Thereby we prove a strong connection between iterated linear control and iterated one-turn pushdowns. In particular, we characterize the members of the geometric language hierarchy (where \u00a3(S) is the class of context-free languages) by iterated one-turn pushdown automata in which the innermost pushdown is unrestricted.", 
    "editor": [
      {
        "familyName": "Budach", 
        "givenName": "Lothar", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/bfb0028831", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "3-540-15689-5"
      ], 
      "name": "Fundamentals of Computation Theory", 
      "type": "Book"
    }, 
    "keywords": [
      "language classes", 
      "context-free grammar G", 
      "class of languages", 
      "language hierarchy", 
      "corresponding words", 
      "grammar G", 
      "linear grammars", 
      "language", 
      "control language", 
      "pushdown automata", 
      "st step", 
      "applied rules", 
      "control strings", 
      "strong connection", 
      "pushdown", 
      "grammar", 
      "words", 
      "hierarchy", 
      "automata", 
      "class", 
      "rules", 
      "connection", 
      "labels", 
      "strings", 
      "members", 
      "types", 
      "storage types", 
      "step", 
      "derivation", 
      "configuration", 
      "results", 
      "control", 
      "terminals", 
      "linear control", 
      "one-turn"
    ], 
    "name": "Iterated linear control and iterated one-turn pushdowns", 
    "pagination": "474-484", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1040495377"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bfb0028831"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/bfb0028831", 
      "https://app.dimensions.ai/details/publication/pub.1040495377"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:42", 
    "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_149.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/bfb0028831"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

94 TRIPLES      23 PREDICATES      61 URIs      54 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bfb0028831 schema:about anzsrc-for:20
2 anzsrc-for:2004
3 schema:author Nd3d8c92de90b4a328267af71aba9ba6d
4 schema:datePublished 1985
5 schema:datePublishedReg 1985-01-01
6 schema:description For a class of languages £, an £-controlled linear grammar K consists of a linear context-free grammar G and a control language H in £, where the terminals of H are interpreted as the labels of rules of G. The language generated by K is obtained by derivations of G such that the corresponding words of applied rules are control strings in H. The control of linear grammars can be iterated by starting with £ and by taking the result of the k-th step as class of control languages for the (k+1)-st step. The language class obtained by the k-th step is denoted by CTRLk (£). Denote by £(S) the language class accepted by nondeterministic one-way S automata, where S is a storage type. We prove that for any S, CTRLk(£(S))=£(Pltk (S)), where Pltk(S) is the storage type of which the configurations consist of k-iterated one-turn pushdowns of S-configurations, i.e., one-turn pushdowns of one-turn pushdowns of … of one-turn pushdowns of S-configurations (k times). Thereby we prove a strong connection between iterated linear control and iterated one-turn pushdowns. In particular, we characterize the members of the geometric language hierarchy (where £(S) is the class of context-free languages) by iterated one-turn pushdown automata in which the innermost pushdown is unrestricted.
7 schema:editor Ne9b56e86105244f2b83b781d7af3781b
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nc63ff695b4ff4deeb9ad722777fab8d5
12 schema:keywords applied rules
13 automata
14 class
15 class of languages
16 configuration
17 connection
18 context-free grammar G
19 control
20 control language
21 control strings
22 corresponding words
23 derivation
24 grammar
25 grammar G
26 hierarchy
27 labels
28 language
29 language classes
30 language hierarchy
31 linear control
32 linear grammars
33 members
34 one-turn
35 pushdown
36 pushdown automata
37 results
38 rules
39 st step
40 step
41 storage types
42 strings
43 strong connection
44 terminals
45 types
46 words
47 schema:name Iterated linear control and iterated one-turn pushdowns
48 schema:pagination 474-484
49 schema:productId N0f22049f3a4b4608970017e07958fa9d
50 N9d4bf4aae6dd4cf48ea05538025a0e48
51 schema:publisher Nf70b021a5de2471b9399a760199b2b65
52 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040495377
53 https://doi.org/10.1007/bfb0028831
54 schema:sdDatePublished 2022-05-20T07:42
55 schema:sdLicense https://scigraph.springernature.com/explorer/license/
56 schema:sdPublisher N5f0ec0329e9d42bebaaf04bdd576e8dc
57 schema:url https://doi.org/10.1007/bfb0028831
58 sgo:license sg:explorer/license/
59 sgo:sdDataset chapters
60 rdf:type schema:Chapter
61 N0f22049f3a4b4608970017e07958fa9d schema:name doi
62 schema:value 10.1007/bfb0028831
63 rdf:type schema:PropertyValue
64 N5f0ec0329e9d42bebaaf04bdd576e8dc schema:name Springer Nature - SN SciGraph project
65 rdf:type schema:Organization
66 N934f905fe44d452c82c9126d94c8f325 schema:familyName Budach
67 schema:givenName Lothar
68 rdf:type schema:Person
69 N9d4bf4aae6dd4cf48ea05538025a0e48 schema:name dimensions_id
70 schema:value pub.1040495377
71 rdf:type schema:PropertyValue
72 Nc63ff695b4ff4deeb9ad722777fab8d5 schema:isbn 3-540-15689-5
73 schema:name Fundamentals of Computation Theory
74 rdf:type schema:Book
75 Nd3d8c92de90b4a328267af71aba9ba6d rdf:first sg:person.014562633673.93
76 rdf:rest rdf:nil
77 Ne9b56e86105244f2b83b781d7af3781b rdf:first N934f905fe44d452c82c9126d94c8f325
78 rdf:rest rdf:nil
79 Nf70b021a5de2471b9399a760199b2b65 schema:name Springer Nature
80 rdf:type schema:Organisation
81 anzsrc-for:20 schema:inDefinedTermSet anzsrc-for:
82 schema:name Language, Communication and Culture
83 rdf:type schema:DefinedTerm
84 anzsrc-for:2004 schema:inDefinedTermSet anzsrc-for:
85 schema:name Linguistics
86 rdf:type schema:DefinedTerm
87 sg:person.014562633673.93 schema:affiliation grid-institutes:grid.5132.5
88 schema:familyName Vogler
89 schema:givenName Heiko
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014562633673.93
91 rdf:type schema:Person
92 grid-institutes:grid.5132.5 schema:alternateName University of Leiden, P.O.Box 9512, 2300 RA, Leiden, The Netherlands
93 schema:name University of Leiden, P.O.Box 9512, 2300 RA, Leiden, The Netherlands
94 rdf:type schema:Organization
 




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


...