Article

Free access

A recognition algorithm for pushdown store systems

Authors:

Alfred V. Aho,

John E. Hopcroft,

Jeffrey D. UllmanAuthors Info & Claims

ACM '68: Proceedings of the 1968 23rd ACM national conference

Pages 597 - 604

https://doi.org/10.1145/800186.810623

Published: 01 January 1968 Publication History

PDF eReader

Abstract

A pushdown store is a list in which information can be accessed only on a last-in first-out principle of operation. The use of pushdown stores is an important technique in the construction of compilers and other language-processing devices.

Of particular interest from both practical and theoretical considerations is how the time and memory required to process a language is functionally related to the length of the input sentence under consideration. In this paper we consider languages which can be defined by pushdown store systems. To obtain quantitative results, a two-way (off-line) nondeterministic pushdown automaton (2N PDA, for short) is used as an analytical model of a pushdown store system, and the two-way deterministic push-down automaton (2D PDA, for short) is also considered as a special case.

References

[1]

N CHOMSKY Context-free grammars and pushdown storage Quarterly Progressive Report No 65 Research Laboratory of Electronics Massachusetts Institute of Technology 1962

Google Scholar

[2]

S GINSBURG S A GREIBACH Deterministic context-free languages Inform Control 9 1966 620-648

Crossref

Google Scholar

[3]

J HARTMANIS R E STEARNS On the computational complexity of algorithms Trans Am Math Soc 117 1965 285-306

Crossref

Google Scholar

[4]

A V AHO J E HOPCROFT J D ULLMAN Time and tape complexity of pushdown automaton languages To appear in Information and Control

Google Scholar

[5]

D YOUNGER Recognition and parsing of context free languages in time n3 Inform Control 10 1967 189-208

Crossref

Google Scholar

[6]

P M LEWIS II R E STEARNS J HARTMANIS Memory bounds for recognition of context-free and context sensitive languages 1965 IEEE Record Switching Circ Theory and Log Des 1965 pp 191-202

Google Scholar

[7]

R E STEARNS J HARTMANIS P M LEWIS II Hierarchies of memory limited computations 1965 IEEE Conf Record Switching Circ Theory and Log Des 1965 pp 179-190

Google Scholar

[8]

J N GRAY M A HARRISON O IBARRA Two-way pushdown automata Inform Contro 11 1967 pp 30-70

Crossref

Google Scholar

[9]

J EARLEY An n2-recognizer for context free grammars Department of Computer Science Carnegie-Mellon University 1967

Google Scholar

Index Terms

A recognition algorithm for pushdown store systems
1. Theory of computation
  1. Formal languages and automata theory
  2. Models of computation
    1. Computability
      1. Turing machines

Recommendations

Descriptional complexity of pushdown store languages

It is well known that the pushdown store language P(M) of a pushdown automaton (PDA) M- i.e., the language consisting of words occurring on the pushdown along accepting computations of M - is a regular language. Here, we design succinct nondeterministic ...
Flip-pushdown automata: nondeterminism is better than determinism
DLT'03: Proceedings of the 7th international conference on Developments in language theory

Flip-pushdown automata are pushdown automata with the additional ability to flip or reverse its pushdown. We investigate deterministic and nondeterministic flip-pushdown automata accepting by final state or empty pushdown. In particular, for ...
Reversible pushdown automata

Reversible pushdown automata are deterministic pushdown automata that are also backward deterministic. Therefore, they have the property that any configuration occurring in any computation has exactly one predecessor. In this paper, the computational ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM '68: Proceedings of the 1968 23rd ACM national conference

January 1968

821 pages

ISBN:9781450374866

DOI:10.1145/800186

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1968

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
55
Total Downloads

Downloads (Last 12 months)22
Downloads (Last 6 weeks)3

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Index Terms

Recommendations

Descriptional complexity of pushdown store languages

Flip-pushdown automata: nondeterminism is better than determinism

Reversible pushdown automata