On the recognition of context-free languages View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1985

AUTHORS

Wojciech Rytter

ABSTRACT

In this paper we present two results concerning the time and space complexity of context-free recognition. The first result states that cfl's can be recognized on a cube-connected computer (CCC) or on a perfect-shuffle computer (PSC) in log2n time using n6 processors. There are known algorithms with the same parallel time complexity but they use more powerful models of computation. The second result states that deterministic cfl's can be recognized in polynomial time using one log2n bounded pushdown store and log n tape. Known algorithms use log2n tape. Since algorithm is a simulation of a deterministic pda it may be looked upon as an efficient reduction of the height of the pushdown store. The second result is obtained by applying a transformation of a fast parallel recognition of deterministic cfl's and it can be viewed as an application of parallel algorithms to the design of efficient sequential algorithms.Both results are aimed not at improving the known complexity bounds, but rather at showing that the same complexity can be obtained on less powerful models of computation. More... »

PAGES

318-325

Book

TITLE

Computation Theory

ISBN

978-3-540-16066-3
978-3-540-39748-9

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-16066-3_26

DOI

http://dx.doi.org/10.1007/3-540-16066-3_26

DIMENSIONS

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


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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Institute of Informatics, Warsaw University, Poland", 
          "id": "http://www.grid.ac/institutes/grid.12847.38", 
          "name": [
            "Institute of Informatics, Warsaw University, Poland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rytter", 
        "givenName": "Wojciech", 
        "id": "sg:person.013534566577.61", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013534566577.61"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1985", 
    "datePublishedReg": "1985-01-01", 
    "description": "In this paper we present two results concerning the time and space complexity of context-free recognition. The first result states that cfl's can be recognized on a cube-connected computer (CCC) or on a perfect-shuffle computer (PSC) in log2n time using n6 processors. There are known algorithms with the same parallel time complexity but they use more powerful models of computation. The second result states that deterministic cfl's can be recognized in polynomial time using one log2n bounded pushdown store and log n tape. Known algorithms use log2n tape. Since algorithm is a simulation of a deterministic pda it may be looked upon as an efficient reduction of the height of the pushdown store. The second result is obtained by applying a transformation of a fast parallel recognition of deterministic cfl's and it can be viewed as an application of parallel algorithms to the design of efficient sequential algorithms.Both results are aimed not at improving the known complexity bounds, but rather at showing that the same complexity can be obtained on less powerful models of computation.", 
    "editor": [
      {
        "familyName": "Skowron", 
        "givenName": "Andrzej", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-16066-3_26", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-16066-3", 
        "978-3-540-39748-9"
      ], 
      "name": "Computation Theory", 
      "type": "Book"
    }, 
    "keywords": [
      "perfect shuffle computer", 
      "deterministic CFLs", 
      "parallel time complexity", 
      "efficient sequential algorithm", 
      "context-free recognition", 
      "parallel algorithm", 
      "time complexity", 
      "space complexity", 
      "pushdown store", 
      "sequential algorithm", 
      "parallel recognition", 
      "polynomial time", 
      "log2n time", 
      "powerful model", 
      "complexity bounds", 
      "context-free languages", 
      "algorithm", 
      "same complexity", 
      "second result states", 
      "computer", 
      "complexity", 
      "first result states", 
      "computation", 
      "recognition", 
      "processors", 
      "n tape", 
      "deterministic PDA", 
      "result states", 
      "stores", 
      "PDA", 
      "language", 
      "log2n", 
      "model", 
      "applications", 
      "efficient reduction", 
      "time", 
      "bounds", 
      "CFL", 
      "design", 
      "second result", 
      "simulations", 
      "results", 
      "state", 
      "transformation", 
      "tape", 
      "reduction", 
      "height", 
      "paper"
    ], 
    "name": "On the recognition of context-free languages", 
    "pagination": "318-325", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1044960546"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-16066-3_26"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-16066-3_26", 
      "https://app.dimensions.ai/details/publication/pub.1044960546"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-08-04T17:15", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/chapter/chapter_191.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-16066-3_26"
  }
]
 

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/3-540-16066-3_26'

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/3-540-16066-3_26'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-16066-3_26'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-16066-3_26'


 

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

107 TRIPLES      22 PREDICATES      73 URIs      66 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-16066-3_26 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N3c438a11e7f547d7bcb247945ad1e546
4 schema:datePublished 1985
5 schema:datePublishedReg 1985-01-01
6 schema:description In this paper we present two results concerning the time and space complexity of context-free recognition. The first result states that cfl's can be recognized on a cube-connected computer (CCC) or on a perfect-shuffle computer (PSC) in log2n time using n6 processors. There are known algorithms with the same parallel time complexity but they use more powerful models of computation. The second result states that deterministic cfl's can be recognized in polynomial time using one log2n bounded pushdown store and log n tape. Known algorithms use log2n tape. Since algorithm is a simulation of a deterministic pda it may be looked upon as an efficient reduction of the height of the pushdown store. The second result is obtained by applying a transformation of a fast parallel recognition of deterministic cfl's and it can be viewed as an application of parallel algorithms to the design of efficient sequential algorithms.Both results are aimed not at improving the known complexity bounds, but rather at showing that the same complexity can be obtained on less powerful models of computation.
7 schema:editor N391fb920a2c14f2699d87c66868f07d6
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N49eee4f349004295ad037747df36457b
11 schema:keywords CFL
12 PDA
13 algorithm
14 applications
15 bounds
16 complexity
17 complexity bounds
18 computation
19 computer
20 context-free languages
21 context-free recognition
22 design
23 deterministic CFLs
24 deterministic PDA
25 efficient reduction
26 efficient sequential algorithm
27 first result states
28 height
29 language
30 log2n
31 log2n time
32 model
33 n tape
34 paper
35 parallel algorithm
36 parallel recognition
37 parallel time complexity
38 perfect shuffle computer
39 polynomial time
40 powerful model
41 processors
42 pushdown store
43 recognition
44 reduction
45 result states
46 results
47 same complexity
48 second result
49 second result states
50 sequential algorithm
51 simulations
52 space complexity
53 state
54 stores
55 tape
56 time
57 time complexity
58 transformation
59 schema:name On the recognition of context-free languages
60 schema:pagination 318-325
61 schema:productId N5532c556b05f4cfebbfeb2cbd3f62139
62 Nc2852ddc53be429ab768c026f3d71cf0
63 schema:publisher Nb1b5fd0937334410b5d43ba21b6bad60
64 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044960546
65 https://doi.org/10.1007/3-540-16066-3_26
66 schema:sdDatePublished 2022-08-04T17:15
67 schema:sdLicense https://scigraph.springernature.com/explorer/license/
68 schema:sdPublisher N912f1465942a4857a72a4bbc67ccfb1b
69 schema:url https://doi.org/10.1007/3-540-16066-3_26
70 sgo:license sg:explorer/license/
71 sgo:sdDataset chapters
72 rdf:type schema:Chapter
73 N391fb920a2c14f2699d87c66868f07d6 rdf:first N65d9706cc9734f288e38179280be27fd
74 rdf:rest rdf:nil
75 N3c438a11e7f547d7bcb247945ad1e546 rdf:first sg:person.013534566577.61
76 rdf:rest rdf:nil
77 N49eee4f349004295ad037747df36457b schema:isbn 978-3-540-16066-3
78 978-3-540-39748-9
79 schema:name Computation Theory
80 rdf:type schema:Book
81 N5532c556b05f4cfebbfeb2cbd3f62139 schema:name doi
82 schema:value 10.1007/3-540-16066-3_26
83 rdf:type schema:PropertyValue
84 N65d9706cc9734f288e38179280be27fd schema:familyName Skowron
85 schema:givenName Andrzej
86 rdf:type schema:Person
87 N912f1465942a4857a72a4bbc67ccfb1b schema:name Springer Nature - SN SciGraph project
88 rdf:type schema:Organization
89 Nb1b5fd0937334410b5d43ba21b6bad60 schema:name Springer Nature
90 rdf:type schema:Organisation
91 Nc2852ddc53be429ab768c026f3d71cf0 schema:name dimensions_id
92 schema:value pub.1044960546
93 rdf:type schema:PropertyValue
94 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
95 schema:name Information and Computing Sciences
96 rdf:type schema:DefinedTerm
97 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
98 schema:name Computation Theory and Mathematics
99 rdf:type schema:DefinedTerm
100 sg:person.013534566577.61 schema:affiliation grid-institutes:grid.12847.38
101 schema:familyName Rytter
102 schema:givenName Wojciech
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013534566577.61
104 rdf:type schema:Person
105 grid-institutes:grid.12847.38 schema:alternateName Institute of Informatics, Warsaw University, Poland
106 schema:name Institute of Informatics, Warsaw University, Poland
107 rdf:type schema:Organization
 




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


...