×

zbMATH — the first resource for mathematics

Two decidability results for deterministic pushdown automata. (English) Zbl 0399.03023

MSC:
03D05 Automata and formal grammars in connection with logical questions
03B25 Decidability of theories and sets of sentences
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Friedman, E.P., The inclusion problem for simple languages, Theoret. comput. sci., 1, 297-316, (1976) · Zbl 0349.68032
[2] Harrison, M.A.; Havel, I.M., Strict deterministic grammars, J. comput. system. sci., 7, 237-277, (1973) · Zbl 0261.68036
[3] Jaffe, V.A., Two classes of CF-languages with a solvable equivalence problem, Kibernetika (kiev), 2, 89-93, (1974), (in Russian)
[4] Korenjak, A.J.; Hopcroft, J.E., Simple deterministic languages, (), 36-46 · Zbl 0313.68061
[5] Kriegel, H.P.; Maurer, H.A., Formal translations and szilard languages, Inform. contr., 30, 187-198, (1976) · Zbl 0322.68053
[6] Kriegel, H.P.; Ottmann, Th., Left-Fitting translations, (1976), manuscript · Zbl 0353.68079
[7] Moriya, E., The associate language and the derivation properties of formal grammars, Inform. contr., 22, 139-162, (1973) · Zbl 0254.68017
[8] Penttonen, M., On derivation languages corresponding to context-free grammars, Acta informatica, 3, 285-291, (1974) · Zbl 0268.68033
[9] Rosenkrantz, D.J.; Stearns, R.E., Properties of deterministic topdown grammars, Inform. contr., 17, 226-255, (1970) · Zbl 0209.02703
[10] 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
[11] Valiant, L.G., Decision problems for families of deterministic pushdown automata, (1973), Univ. of Warwick Computer Centre, Report No. 7 · Zbl 0341.94030
[12] Valiant, L.G., The equivalence problem for deterministic finite-turn pushdown automata, Inform. contr., 25, 123-133, (1974) · Zbl 0285.68025
[13] 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.