×
Gallier, Jean H.

DPDA’s in ’Atomic normal form’ and applications to equivalence problems. (English) Zbl 0474.68065

Theor. Comput. Sci. 14, 155-186 (1981).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0474.68065

Cited in 2 Reviews
Cited in 12 Documents

MSC:

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

Keywords:

address language; recursion schemes; deterministic pushdown automata; encoding of trees

Citations:

Zbl 0377.68040; Zbl 0428.68088; Zbl 0393.68078
Cite Review PDF
Full Text: DOI

References:

[1] Berri, 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] Brosgol, B., Deterministic translation grammars, (Ph.D. thesis (1974), Harvard University)
[3] Courcelle, B., Sur les ensembles algébriques d’arbres et les langages déterministes, quelques applications à la théorie des schemas de programmes, (Thèse (1976), Université de Paris-7)
[4] Courcelle, B., A representation of trees by languages, II, Theoret. Comput. Sci., 7, 25-55 (1978) · Zbl 0428.68088
[5] Courcelle, B., On jump-deterministic pushdown automata, Math. Systems Theory, 11, 87-109 (1977) · Zbl 0365.02021
[6] Courcelle, B.; Nivat, M., Algebraic families of interpretations, Proc. 17th Annual Symposium on F.O.C.S. (1976), Houston
[7] Courcelle, B.; Vuillemin, J., Completeness results for the equivalence of recursive schemes, J. Comput. System Sci., 12, 2, 179-197 (1976) · Zbl 0342.68008
[8] DeBakker, J. W.; Scott, D., A theory of programs (1969), IBM Seminar: IBM Seminar Vienna, unpublished notes
[9] Engelfriet, J., Simple Program Schemes and Formal Languages, (Lecture Notes in Computer Science, 20 (1974), Springer: Springer Berlin) · Zbl 0288.68030
[10] Engelfriet, J.; Schmidt, E., IO and OI, II, J. Comput. System Sci., 16, 1 (1978) · Zbl 0371.68020
[11] Friedman, E. P., The inclusion problem for simple languages, Theoret. Comput. Sci., 1, 297-316 (1976) · Zbl 0349.68032
[12] Friedman, E. P., Equivalence problems for deterministic context-free languages and monadic recursion schemes, J. Comput. System Sci., 14, 344-359 (1977) · Zbl 0358.68109
[13] Friedman, E. P., Simple context-free languages and free monadic recursion schemes, Math. System Theory, 11, 9-28 (1977) · Zbl 0364.68076
[14] Friedman, E. P.; Greibach, S. A., Superdeterministic DPDA’s: The method of accepting does affect decision problems, J. Comput. System Sci., 19, 1, 79-117 (1979) · Zbl 0419.68100
[15] J.H. Gallier, Recursion schemes and algebraic theories, to appear.; J.H. Gallier, Recursion schemes and algebraic theories, to appear. · Zbl 0472.68006
[16] Gallier, J. H., Recursion schemes and generalized interpretations, (Automata, Languages and Programming. Automata, Languages and Programming, Lecture Notes in Computer Science, 71 (1979), Springer: Springer Berlin), 256-270 · Zbl 0409.68014
[17] Ginali, S., Iterative algebraic theories, infinite trees and program schemata, (Ph.D. thesis (1976), University of Chicago)
[18] Ginali, S., Regular trees and the free iterative theory, J. Comput. System Sci., 18, 3, 228-242 (1979) · Zbl 0495.68042
[19] Gorn, S., Processors for infinite codes of the Shannon-Fano type, (Proc. Symposium on Mathematical Theory of Automata (1962), Polytechnic Institute of Brooklyn) · Zbl 0116.09604
[20] Gorn, S., Explicit definitions and linguistic dominoes, (Hart, J.; Takasu, S., Systems and Computer Science (1965))
[21] Goguen, J.; Thatcher, J.; Wagner, E.; Wright, J., Initial algebra semantics, J. ACM, 24, 68-95 (1977) · Zbl 0359.68018
[22] Harrison, M. A., Introduction to Formal Language Theory (1978), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0411.68058
[23] Harrison, M. A.; Havel, I. M., Strict deterministic grammars, J. Comput. System Sci., 7, 237-277 (1973) · Zbl 0261.68036
[24] Harrison, M. A.; Havel, I. M., On the parsing of deterministic languages, J. ACM, 21, 525-548 (1974) · Zbl 0296.68084
[25] Nivat, M., On the interpretation of recursive polyadic program schemes, (Symposia Mathematica, 15 (1975), Academic Press: Academic Press New York), 255-281 · Zbl 0346.68041
[26] Oyamaguchi, M.; Honda, N., The decidability of equivalence for deterministic stateless pushdown automata, Information and Control, 38, 367-376 (1978) · Zbl 0393.68078
[27] M. Oyamaguchi, Y. Inagaki and N. Honda, The equivalence problem for real-time strict deterministic languages, Information and Control; M. Oyamaguchi, Y. Inagaki and N. Honda, The equivalence problem for real-time strict deterministic languages, Information and Control · Zbl 0444.68038
[28] Rosen, B., Tree-manipulating systems and Church-Rosser theorems, J. ACM, 20, 160-187 (1973) · Zbl 0267.68013
[29] Rosen, B., Program equivalence and context-free grammars, J. Comput. System Sci., 11, 358-374 (1975) · Zbl 0315.68063
[30] Solomon, Type definitions with parameters, Proc. 5th Annual ACM Symposium on Principles of Programming Languages (1978), Tucson, Arizona
[31] 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
[32] Valiant, L. G., Decision procedures for families of deterministic pushdown automata, (Ph.D. thesis (1973), University of Warwick: University of Warwick U.K) · Zbl 0566.94022
[33] Valiant, L. G., The equivalence problem for deterministic finite-turn pushdown automata, Information and Control, 25, 123-133 (1975) · Zbl 0285.68025
[34] Valiant, L. G.; Paterson, M. S., Deterministic one-counter automata, J. Comput. System Sci., 10, 340-350 (1975) · Zbl 0307.68038
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.