×

zbMATH — the first resource for mathematics

Characterizations of stack uniform strict deterministic languages. (English) Zbl 0468.68090

MSC:
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: EuDML
References:
[1] A. V. Aho J. D. Ullman: The Theory of Parsing, Translation, and Compiling. Vols. I, II. Prentice Hall, Englewood Cliffs, N. J. 1972, 1973.
[2] E. P. Friedman: The inclusion problem for simple languages. Theoretical Computer Science 7 (1976), 297-316. · Zbl 0349.68032
[3] J. N. Gray M. A. Harrison: On the covering and reduction problems for context-free grammars. J. ACM 19 (1972), 675-698. · Zbl 0259.68035
[4] M. A. Harrison I. M. Havel: Strict deterministic grammars. Journal of Computer and System Sciences 7 (1973), 237-277. · Zbl 0261.68036
[5] M. A. Harrison I. M. Havel: Real-time strict deterministic languages. SIAM Journal on Computing 1 (1972), 333-349. · Zbl 0267.68034
[6] A. J. Korenjak J. E. Hopcroft: Simple deterministic languages. IEEE Conference Record of the 7th Annual Symposium on Switching and Automata Theory (1966), 36 - 46. · Zbl 0313.68061
[7] M. Linna: Two decidability results for deterministic pushdown automata. Journal of Computer and System Sciences 18 (1979), 92-107. · Zbl 0399.03023
[8] R. McNaughton: Parenthesis grammars. J. ACM 14 (1967), 490-500. · Zbl 0168.01206
[9] M. Oyamaguchi N. Honda Y. Inagaki: The equivalence problem for real-time strict deterministic languages. Information and Control 45 (1980), 90-115. · Zbl 0444.68038
[10] J. Pittl: On two subclasses of real-time grammars. Mathematical Foundations of Computer Science 1978 (J. Winkowski. Lecture Notes in Computer Science 64, Springer-Verlag, Berlin 1978, 426-435. · Zbl 0389.68041
[11] L. G. Valiant: Decision Problems for Families of Deterministic Pushdown Automata. University of Warwick, Computer Centre, Report No. 7, 1973.
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.