The inclusion problem for simple languages. (English) Zbl 0349.68032


68Q45 Formal languages and automata
Full Text: DOI


[1] Aho, A.V.; Ullman, J.D., The theory of parsing, translation, and compiling, () · Zbl 0196.01702
[2] Ashcroft, E.; Manna, Z.; Pnueli, A., Decibale properties of monadic functional schemas, J. ACM, 20, 3, 489-499, (1973) · Zbl 0289.68036
[3] Bird, M., The equivalence problem for deterministic two-tape automata, J. comput. system sci., 7, 218-236, (1973) · Zbl 0271.94039
[4] DeBakker, J.W.; Scott, D., A theory of programs, (August 1969), unpublished memo, Vienna
[5] Friedman, E.P., Equivalence problems in monadic recursion schemas, (), 26-33
[6] Ginsburg, S., The mathematical theory of context-free languages, (1966), McGraw-Hill New York · Zbl 0184.28401
[7] Harrison, M.A.; Havel, I.M., Real-time strict deterministic languages, SIAM J. comput., 1, 333-349, (1972) · Zbl 0267.68034
[8] Hopcroft, J.E.; Ullman, J.D., Formal languages and their relation to automata, (1968), Addison-Wesley Reading, Mass · Zbl 0155.34302
[9] A.J. Korenjak and J.E. Hopcroft, Simple deterministic languages, IEEE Conf. Record of 7th Annual Symp. on Switching and Automata Theory, 36-46. · Zbl 0313.68061
[10] Rabin, M.O.; Scott, D., Finite automata and their decision problems, (), 63-91 · Zbl 0158.25404
[11] Rosenkrantz, D.J.; Stearns, R.E., Properties of deterministic top-down grammars, Information and control, 17, 3, 226-256, (1970) · Zbl 0209.02703
[12] Valiant, L.G., Decision procedures for families of deterministic pushdown automata, () · Zbl 0566.94022
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.