×

An extended direct branching algorithm for checking equivalence of deterministic pushdown automata. (English) Zbl 0552.68065

This paper extends the author’s direct branching algorithm [Inf. Control. 52, 187-238 (1982; Zbl 0541.68053)] for checking equivalence of deterministic pushdown automata. It does so by providing a technique called ’halting’ for dealing with nodes with unbounded degree in the comparison tree. This may occur when a skipping step may be applied infinitely many times to a certain node, as a result of infinite sequences of \(\epsilon\)-moves. This extension allows the algorithm to check equivalence of the deterministic pushdown automata when none of them is real-time, but in a certain condition that properly contains a case where one of them is real-time strict.

MSC:

68Q45 Formal languages and automata
68Q05 Models of computation (Turing machines, etc.) (MSC2010)

Citations:

Zbl 0541.68053
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beeri, C., An improvement on Valiant’s decision procedure for equivalence of deterministic finite turn pushdown machines, Theoret. Comput. Sci., 3, 305-320 (1976) · Zbl 0361.68082
[2] Courcelle, B., A representation of trees by languages I, Theoret. Comput. Sci., 6, 255-279 (1978) · Zbl 0377.68040
[3] Courcelle, B., The simultaneous accessibility of two configurations of two equivalent dpda’s, Inform. Process. Lett., 12, 111-114 (1981) · Zbl 0459.68019
[4] Courcelle, B., An axiomatic approach to the Korenjak-Hopcroft algorithms, Math. Systems Theory, 16, 191-231 (1983) · Zbl 0581.68032
[5] Friedman, E. P.; Greibach, S. A., Superdeterministic DPDAs: The method of accepting does affect decision problems, J. Comput. System Sci., 19, 79-117 (1979) · Zbl 0419.68100
[6] Friedman, E. P.; Greibach, S. A., A polynomial time algorithm for deciding the equivalence problem for 2-tape deterministic finite state acceptors, SIAM J. Comput., 11, 166-183 (1982) · Zbl 0497.68050
[7] Harrison, M. A.; Havel, I. M., Real-time strict deterministic languages, SIAM J. Comput., 1, 333-349 (1972) · Zbl 0267.68034
[8] Harrison, M. A.; Havel, I. M.; Yehudai, A., On equivalence of grammars through transformation trees, Theoret. Comput. Sci., 9, 173-205 (1979) · Zbl 0409.68041
[9] Itzhaik, Y.; Yehudai, A., A decision procedure for the equivalence of two dpda’s one of which is linear, (Lecture Notes in Comput. Sci., 115 (1981), Springer: Springer Berlin), 229-237 · Zbl 0469.68057
[10] Katayama, T.; Tsachiya, N.; Enomoto, H., On the decidability of equivalence for deterministic pushdown transducers, Trans. Inst. Electron. Commun. Engrs. Japan, 58-D, 760-767 (1975)
[11] Korenjak, A. J.; Hopcroft, J. E., Simple deterministic languages, Proc. IEEE 7th Ann. Symp. on Switching and Automata Theory, 36-46 (1966) · Zbl 0313.68061
[12] Linna, M., Two decidability results for deterministic pushdown automata, J. Comput. System Sci., 18, 92-107 (1979) · Zbl 0399.03023
[13] Olshansky, T.; Pnueli, A., A direct algorithm for checking equivalence of LL \((k)\) grammars, Theoret. Comput. Sci., 4, 321-349 (1977) · Zbl 0358.68118
[14] Oyamaguchi, M.; Honda, N., The decidability of equivalence for deterministic stateless pushdown automata, Inform. Control, 38, 367-376 (1978) · Zbl 0393.68078
[15] Oyamaguchi, M.; Honda, N.; Inagaki, Y., The equivalence problem for real-time strict deterministic languages, Inform. Control, 45, 90-115 (1980) · Zbl 0444.68038
[16] Oyamaguchi, M., Some results on equivalence and subclass containment problems for DPDA’s, Proc. 5th IBM Symp. on Mathematical Foundations of Computer Science (1980)
[17] Oyamaguchi, M.; Inagaki, Y.; Honda, N., On the equivalence problem for two dpda’s, one of which is real-time, Proc. IFIP Congress 80, 53-57 (1980) · Zbl 0443.68037
[18] Oyamaguchi, M.; Inagaki, Y.; Honda, N., The equivalence problem for two dpda’s, one of which is a finite-turn or one-counter machine, J. Comput. System Sci., 23, 366-382 (1981) · Zbl 0473.68046
[19] Reingold, E. M.; Nievergelt, J.; Deo, N., Combinatorial Algorithms: Theory and Practice (1977), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0367.68032
[20] Rosenkrantz, D. J.; Stearns, R. E., Properties of deterministic top-down grammars, Inform. Control, 17, 226-256 (1970) · Zbl 0209.02703
[21] Sekimoto, S., An extended result on the equivalence problem for LR machines taking monotonous ϵ-moves, Trans. Inst. Electron. Commun. Engrs. Japan, J64-D, 419-426 (1981)
[22] Sekimoto, S., On the equivalence problem for deterministic finite-turn pushdown automata, Trans. Inst. Electron. Commun. Engrs. Japan, J64-D, 463-470 (1981)
[23] Sekimoto, S., A restricted result on the equivalence problem for deterministic pushdown automata, Trans. Inst. Electron. Commun. Engrs. Japan, J64-D, 661-668 (1981)
[24] Taniguchi, K.; Kasami, T., A result on the equivalence problem for deterministic pushdown automata, J. Comput. System Sci., 13, 38-50 (1976) · Zbl 0337.68032
[25] Tomita, E., A direct branching algorithm for checking equivalence of some classes of deterministic pushdown automata, Inform. Control, 52, 187-238 (1982) · Zbl 0541.68053
[26] Tomita, E., A direct branching algorithm for checking equivalence of strict deterministic vs. LL \((k)\) grammars, Theoret. Comput. Sci., 23, 129-154 (1983) · Zbl 0509.68072
[27] Ukkonen, E., The equivalence problem for some non-real-time deterministic pushdown automata, J. Assoc. Comput. Mach., 29, 1166-1181 (1982) · Zbl 0489.68075
[28] Valiant, L. G., Decision procedures for families of deterministic pushdown automata, (Ph.D. Thesis (1973), Department of Computer Science, University of Warwick) · Zbl 0566.94022
[29] Valiant, L. G., The decidability of equivalence for deterministic finite-turn pushdown automata, Inform. Control, 25, 123-133 (1974) · Zbl 0285.68025
[30] Valiant, L. G.; Paterson, M. S., Deterministic one-counter automata, J. Comput. System Sci., 10, 340-350 (1975) · Zbl 0307.68038
[31] Wood, D., Some remarks on the KH algorithm for \(s\)-grammars, BIT, 13, 476-489 (1973) · Zbl 0301.68080
[32] Yehudai, A., A hierarchy of real-time deterministic languages and their equivalence, J. Comput. System Sci., 24, 91-100 (1982) · Zbl 0487.68068
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.