×

zbMATH — the first resource for mathematics

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

MSC:
68Q45 Formal languages and automata
PDF BibTeX XML Cite
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, (), 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, (), 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] \scS. Greibach, Erasable context-free languages, unpublished manuscript. · 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, (), 207-213
[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, () · 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] \scS. Greibach, Some context-free generators, in preparation. · 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. 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.