article

Deterministic stack automata and the quotient operator

Authors:

J. E. Hopcroft,

J. D. UllmanAuthors Info & Claims

Journal of Computer and System Sciences, Volume 2, Issue 1

Pages 1 - 12

https://doi.org/10.1016/S0022-0000(68)80003-0

Published: 01 June 1968 Publication History

Abstract

A stack automaton is a pushdown automaton with the added privilege of scanning the contents of its pushdown tape without erasing. In this paper, the deterministic stack automaton with a one-way input (dsa) is considered. It is shown that if L is a language accepted by a dsa and R is a regular set, then L/R={w| for some x in R, wx is in L}, is accepted by a dsa. As a corollary, end markers are not needed on the input of the dsa. It is also shown that if L is accepted by a dsa, then Max(L)={w|w in L and for no x is wx is wx in L} is accepted by a dsa.

References

[1]

J. ACM. v14. 172-201.

Google Scholar

[2]

J. ACM. v14. 389-418.

Google Scholar

[3]

Info. Control. v9. 620-648.

Google Scholar

[4]

J. Computers Syst. Sci. v1. 166-186.

Google Scholar

[5]

BST J. v46. 1793-1829.

Google Scholar

Cited By

View all

Kutrib MMeyer U(2023)Tree-Walking-Storage AutomataDevelopments in Language Theory10.1007/978-3-031-33264-7_15(182-194)Online publication date: 12-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-33264-7_15
Amano MIwama KVitter JLarmore LLeighton T(1999)Undecidability on quantum finite automataProceedings of the thirty-first annual ACM symposium on Theory of Computing10.1145/301250.301344(368-375)Online publication date: 1-May-1999
https://dl.acm.org/doi/10.1145/301250.301344
Greibach S(1974)Jump PDA’s and Hierarchies of Deterministic Context-Free LanguagesSIAM Journal on Computing10.1137/02030093:2(111-127)Online publication date: 1-Jun-1974
https://dl.acm.org/doi/10.1137/0203009
Show More Cited By

Deterministic stack automata and the quotient operator
1. Theory of computation

Recommendations

Strictly deterministic CD-systems of restarting automata
FCT'07: Proceedings of the 16th international conference on Fundamentals of Computation Theory

A CD-system of restarting automata is called strictly deterministic if all its component systems are deterministic, and if there is a unique successor system for each component. Here we show that the strictly deterministic CD-systems of restarting ...
Quantum versus deterministic counter automata

This paper focuses on quantum analogues of various models of counter automata, and almost completely proves the relation between the classes of languages recognizable by bounded error quantum ones and classical deterministic ones in every model of ...
Input-Driven stack automata
TCS'12: Proceedings of the 7th IFIP TC 1/WG 202 international conference on Theoretical Computer Science

We introduce and investigate input-driven stack automata, which are a generalization of input-driven pushdown automata that recently became popular under the name visibly pushdown automata. Basically, the idea is that the input letters uniquely ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Computer and System Sciences

Journal of Computer and System Sciences Volume 2, Issue 1

June, 1968

117 pages

ISSN:0022-0000

Issue’s Table of Contents

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 June 1968

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kutrib MMeyer U(2023)Tree-Walking-Storage AutomataDevelopments in Language Theory10.1007/978-3-031-33264-7_15(182-194)Online publication date: 12-Jun-2023
Amano MIwama KVitter JLarmore LLeighton T(1999)Undecidability on quantum finite automataProceedings of the thirty-first annual ACM symposium on Theory of Computing10.1145/301250.301344(368-375)Online publication date: 1-May-1999
Greibach S(1974)Jump PDA’s and Hierarchies of Deterministic Context-Free LanguagesSIAM Journal on Computing10.1137/02030093:2(111-127)Online publication date: 1-Jun-1974
Greibach SAho ABorodin AConstable RFloyd RHarrison MKarp RStrong H(1973)Jump PDA's, deterministic context-free languages principal AFDLs and polynomial time recognition—(Extended Abstract)Proceedings of the fifth annual ACM symposium on Theory of computing10.1145/800125.804031(20-28)Online publication date: 30-Apr-1973
Hopcroft JUllman J(1969)Formal languages and their relation to automataundefinedOnline publication date: 1-Jan-1969

View Options

View options

Login options

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

Abstract

References

Cited By

Recommendations

Strictly deterministic CD-systems of restarting automata

Quantum versus deterministic counter automata

Input-Driven stack automata

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations