Article

Free access

A decision method for the equivalence of some non-real-time deterministic pushdown automata

Author:

Esko UkkonenAuthors Info & Claims

STOC '80: Proceedings of the twelfth annual ACM symposium on Theory of computing

Pages 29 - 38

https://doi.org/10.1145/800141.804650

Published: 28 April 1980 Publication History

Abstract

A generalization of the alternate stacking procedure of Valiant for deciding the equivalence of some deterministic pushdown automata (dpda) is introduced. To analyze the power of the generalized procedure we define a subclass of dpda's, called the proper dpda's. This class properly contains the non-singular dpda's and the real time strict dpda's, and the corresponding class of languages properly contains the real time strict deterministic languages. The equivalence problem for proper automata is reducible to the problem of deciding whether or not an automaton is proper. The main result of the paper is that the generalized procedure yields an equivalence test for proper dpda's, at least one of which is also a finite-turn machine.

References

[1]

Beeri,C.: An improvement on Valiant's decision procedure for equivalence of deterministic finite-turn pushdown automata. Theoretical Computer Science 3 (1976), 305–320.

[2]

Friedman,E.P.: Equivalence problems for deterministic context-free languages and monadic recursion schemes. J. Comput. System Sci. 14 (1977), 344–359.

[3]

Friedman,E.P.: A note on non-singular deterministic pushdown automata. Theoretical Computer Science 7 (1978), 333–339.

[4]

Friedman,E.P.&S.A.Greibach: Superdeterministic DPDAs: The method of accepting does affect decision problems. J. Comput. System Sci. 19 (1979), 79–117.

[5]

Greibach,S.A.: Linearity is polynomially decidable for realtime pushdown store automata. Information and Control 42 (1979), 27–37.

[6]

Harrison,M.A.&I.M.Havel: Real-time strict deterministic languages. SIAM J. on Computing 1 (1972), 333–349.

Digital Library

[7]

Harrison,M.A., I.M.Havel & A.Yehudai: On equivalence of grammars through transformation trees. Theor. Comp. Sci. 9 (1979), 173–205.

[8]

Hopcroft,J.E.&J.D.Ullman: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading, Mass., 1979.

Digital Library

[9]

Korenjak,A.J.&J.E.Hopcroft: Simple deterministic languages. In: Proc. IEEE 7th Annual Symp. on Switching and Automata Theory, Berkeley, Calif. 1966, pp. 36–46.

Digital Library

[10]

Linna,M.: Two decidability results for deterministic pushdown automata. J. Comput. System Sci. 18 (1979), 92–107.

[11]

Olshansky,T.&A.Pnueli: A direct algorithm for checking equivalence of LL(k) grammars. Theor. Comp. Sci. 4 (1977), 321–349.

[12]

Oyamaguchi,M.&N.Honda: The decidability of equivalence for deterministic stateless pushdown automata. Information and Control 38 (1978), 367–376.

[13]

Oyamaguchi,M., N.Honda&Y.Inagaki: The equivalence problem for real-time strict deterministic languages. Unpublished paper, 1978.

[14]

Rosenkrantz,D.J.&R.E.Stearns: Properties of deterministic top-down grammars. Information and Control 17 (1970), 226–255.

[15]

Taniguchi,K.&T.Kasami: A result on the equivalence problem for deterministic pushdown automata. J. Comp. System Sci. 13 (1976), 38–50.

Digital Library

[16]

Ukkonen,E.: The equivalence problem for some non-real-time deterministic pushdown automata. Report C-1980-9, Dept. of Computer Science, University of Helsinki, 1980.

[17]

Valiant,L.G.: Decision procedures for families of deterministic pushdown automata. Ph.D.Diss., University of Warwick Computer Centre, Report No. 7, 1973.

Digital Library

[18]

Valiant,L.G.: The equivalence problem for deterministic finite-turn pushdown automata. Information and Control 25 (1974), 123–133.

Cited By

Nijholt A(2005)The equivalence problem for LL- and LR-regular grammarsFundamentals of Computation Theory10.1007/3-540-10854-8_32(291-300)Online publication date: 28-Jul-2005
https://doi.org/10.1007/3-540-10854-8_32
Itzhaik Y(2005)A decision procedure for the equivalence of two dpdas one of which is linearAutomata, Languages and Programming10.1007/3-540-10843-2_19(229-237)Online publication date: 25-May-2005
https://doi.org/10.1007/3-540-10843-2_19

Index Terms

A decision method for the equivalence of some non-real-time deterministic pushdown automata
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Theorem proving algorithms
2. Theory of computation
  1. Formal languages and automata theory
  2. Logic
    1. Proof theory

Recommendations

Efficient determinization of visibly and height-deterministic pushdown automata

New algorithms for the determinization of nondeterministic visibly and nondeterministic real-time height-deterministic pushdown automata are presented. The algorithms improve the results of existing algorithms. They construct only accessible states and ...
Deterministic Pushdown Automata and Unary Languages
CIAA '08: Proceedings of the 13th international conference on Implementation and Applications of Automata

The simulation of deterministic pushdown automata defined over a one letter alphabet by finite state automata is investigated from a descriptional complexity point of view. We show that each unary deterministic pushdown automaton of size s can be ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '80: Proceedings of the twelfth annual ACM symposium on Theory of computing

April 1980

446 pages

ISBN:0897910176

DOI:10.1145/800141

Copyright © 1980 ACM.

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 April 1980

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

STOC '80 Paper Acceptance Rate 47 of 125 submissions, 38%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
81
Total Downloads

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

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nijholt A(2005)The equivalence problem for LL- and LR-regular grammarsFundamentals of Computation Theory10.1007/3-540-10854-8_32(291-300)Online publication date: 28-Jul-2005
https://doi.org/10.1007/3-540-10854-8_32
Itzhaik Y(2005)A decision procedure for the equivalence of two dpdas one of which is linearAutomata, Languages and Programming10.1007/3-540-10843-2_19(229-237)Online publication date: 25-May-2005
https://doi.org/10.1007/3-540-10843-2_19

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

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

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents