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 N4a5672b156d34ba3ab68ec3afe19efd3
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 N780ba127a7c34ac6a441d60457bc489e
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N1815ad8032f843e3a3400fc329938ff3
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 N2ce2e2d346cd425d81d85e2b4667f5eb
62 Ne0e4a972761347769df1d48c6c56bc2c
63 schema:publisher Nae6c40be287d45a0b2372d83005b1ed5
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 N3d9d3b5a017b42208ee2033154da8574
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 N1815ad8032f843e3a3400fc329938ff3 schema:isbn 978-3-540-16066-3
74 978-3-540-39748-9
75 schema:name Computation Theory
76 rdf:type schema:Book
77 N2ce2e2d346cd425d81d85e2b4667f5eb schema:name dimensions_id
78 schema:value pub.1044960546
79 rdf:type schema:PropertyValue
80 N3d9d3b5a017b42208ee2033154da8574 schema:name Springer Nature - SN SciGraph project
81 rdf:type schema:Organization
82 N4a5672b156d34ba3ab68ec3afe19efd3 rdf:first sg:person.013534566577.61
83 rdf:rest rdf:nil
84 N780ba127a7c34ac6a441d60457bc489e rdf:first Nf5dd5633f0ce46d1beadbcb76d0adfda
85 rdf:rest rdf:nil
86 Nae6c40be287d45a0b2372d83005b1ed5 schema:name Springer Nature
87 rdf:type schema:Organisation
88 Ne0e4a972761347769df1d48c6c56bc2c schema:name doi
89 schema:value 10.1007/3-540-16066-3_26
90 rdf:type schema:PropertyValue
91 Nf5dd5633f0ce46d1beadbcb76d0adfda schema:familyName Skowron
92 schema:givenName Andrzej
93 rdf:type schema:Person
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)


...