1985
AUTHORS ABSTRACTIn 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... »
PAGES318-325
Computation Theory
ISBN
978-3-540-16066-3
978-3-540-39748-9
http://scigraph.springernature.com/pub.10.1007/3-540-16066-3_26
DOIhttp://dx.doi.org/10.1007/3-540-16066-3_26
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1044960546
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
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 |