×

One counter languages and the IRS condition. (English) Zbl 0307.68062


MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Banerji, R. B., Phrase structure languages, finite machines and channel capacity, Information and Control, 6, 153-162 (1963) · Zbl 0115.37008
[2] Brainerd, B., An analog of a theorem about context-free languages, Information and Control, 11, 561-567 (1968) · Zbl 0184.02601
[3] Chomsky, N.; Schützenberger, M. P., The Algebraic Theory of Context-Free Languages, (Braffort, P.; Hirschberg, D., Computer Programming and Formal Systems (1963), North Holland: North Holland Amsterdam), 118-161 · Zbl 0148.00804
[4] Elgot, C. C.; Mezei, J. E., On relations defined by generalized finite automata, IMB J. Res. Develop., 9, 47-68 (1965) · Zbl 0135.00704
[5] Ginsburg, S.; Greibach, S., Abstract families of languages, (Studies in Abstract Families of Languages. Studies in Abstract Families of Languages, Memoirs of the American Mathematical Society No. 87 (1969)), 1-32, Providence, RI · Zbl 0308.68058
[6] Ginsburg, S.; Spanier, E. H., Derivation-bounded languages, J. Comput. System Sci., 2, 228-250 (1968) · Zbl 0176.16703
[7] Ginsburg, S.; Spanier, E. H., Finite-turn pushdown automata, SIAM J. Control, 4, 429-453 (1966) · Zbl 0147.25302
[8] Greibach, S., Chains of full AFLs, Math. Systems Theory, 4, 231-242 (1970) · Zbl 0203.30102
[9] S. Greibach; S. Greibach · Zbl 0317.68059
[10] Greibach, S., An infinite hierarchy of context-free languages, JACM, 16, 91-106 (1969) · Zbl 0182.02002
[11] Greibach, S.; Ginsburg, S.; Golstine, J., Uniformly erasable AFL, (Proceedings Fourth ACM Symposium, Theory of Computing. Proceedings Fourth ACM Symposium, Theory of Computing, Denver, Colorado (May 1972)), 207-213 · Zbl 0357.68075
[12] Nerode, A., Linear automaton transformations, Proc. Amer. Math. Soc., 9, 541-544 (1958) · Zbl 0089.33403
[13] Nivat, M., Transductions des languages de Chomsky, (Doctoral Dissertation (1967), Grenoble University) · Zbl 0313.68065
[14] Yntema, M. K., Inclusion relations among families of context-free languages, Information and Control, 10, 572-597 (1967) · Zbl 0207.31405
[15] Boasson, L., The inclusion of the substitution closure of linear and one-counter languages in the largest sub-AFL of the family of algebraic languages is proper, Information Processing Letters, 2, 135-140 (1974) · Zbl 0329.68067
[16] S. Greibach; S. Greibach · Zbl 0248.68036
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.