×

One way finite visit automata. (English) Zbl 0368.68059


MSC:

68Q45 Formal languages and automata
03D10 Turing machines and related notions
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Baker, B.S.; Book, R.V., Reversal-bounded multipushdown machines, J. comput. system sci., 8, 315-332, (1974) · Zbl 0309.68043
[2] Banerji, R.B., Phrase structure languages, finite machines and channel capacity, Information and control, 6, 153-162, (1963) · Zbl 0115.37008
[3] Book, R.V.; Greibach, S.A., Quasi-realtime languages, Math. systems theory, 4, 97-111, (1970) · Zbl 0188.33102
[4] Chomsky, N., On certain formal properties of grammars, Information and control, 2, 137-167, (1959) · Zbl 0088.10801
[5] Ehrich, R.W.; Yau, S.S., Two-way sequential transductions and stack automata, Information and control, 18, 404-446, (1971) · Zbl 0222.94063
[6] Elgot, C.C.; Mezei, J.E., On relations defined by generalized finite automata, IBM J. res. develop., 9, 47-68, (1975) · Zbl 0135.00704
[7] Fischer, P.C., The reduction of tape reversal for off-line one-tape Turing machines, J. comput. system sci., 2, 136-147, (1968) · Zbl 0199.31001
[8] Ginsburg, S.; Greibach, S.A.; Ginsburg; Greibach; Hopcroft, Abstract families of languages, Studies in abstract families of languages, mem. amer. math. soc., 87, 1-32, (1969) · Zbl 0194.31402
[9] Ginsburg, S.; Greibach, S., On AFL generators for finitely encoded AFA, J. comput. system sci., 7, 1-27, (1973) · Zbl 0249.68025
[10] Ginsburg, S.; Greibach, S.A., Principal AFL, J. comput. system sci., 4, 308-338, (1970) · Zbl 0198.03102
[11] Ginsburg, S.; Spanier, E.H., AFL with the semilinear property, J. comput. system sci., 5, 365-396, (1971) · Zbl 0235.68029
[12] Ginsburg, S.; Spanier, E.H., Control sets on grammars, Math. systems theory, 2, 159-178, (1968) · Zbl 0157.33604
[13] Ginsburg, S.; Spanier, E.H., Derivation-bounded languages, J. comput. system sci., 2, 228-250, (1968) · Zbl 0176.16703
[14] Ginsburg, S.; Spanier, E.H., Finite-turn pushdown automata, SIAM J. control, 4, 429-453, (1966) · Zbl 0147.25302
[15] Greibach, S.A., Chains of full AFL’s, Math. system theory, 4, 231-242, (1970) · Zbl 0203.30102
[16] Greibach, S.A., Checking automata and one-way stack languages, J. comput. system sci., 3, 196-217, (1969) · Zbl 0174.02702
[17] S.A. Greibach, Control sets on context-free grammar forms, J. Comput. System Sci. (to appear). · Zbl 0359.68093
[18] Greibach, S.A., An infinite hierarchy of context-free languages, J. assoc. comput. Mach., 16, 91-106, (1969) · Zbl 0182.02002
[19] Greibach, S.A., Syntactic operators on full semiafls, J. comput. system sci., 6, 30-76, (1972) · Zbl 0269.68046
[20] S.A. Greibach, Visits, crosses and reversals for nondeterministic offline machines, Information and Control (to appear).
[21] Hartmanis, J., Tape-reversal bounded Turing machine computations, J. comput. system. sci., 2, 117-135, (1968) · Zbl 0259.68020
[22] Nerode, A., Linear automata transformations, Proc. amer. math. soc., 9, 541-544, (1958) · Zbl 0089.33403
[23] Parikh, R.J., On context-free languages, J. assoc. comput. Mach., 13, 570-581, (1966) · Zbl 0154.25801
[24] Rabin, M.O.; Scott, D., Finite automata and their decision problems, IBM J. res. develop., 3, 114-125, (1959) · Zbl 0158.25404
[25] Rajlick, V., Absolutely parallel grammars and two-way finite-state transducers, J. comput. system sci., 6, 324-342, (1972) · Zbl 0246.68013
[26] Rajlich, V., Bounded-crossing transducers, Information and control, 27, 329-335, (1975) · Zbl 0297.68069
[27] Rodriguez, F., Une double hiérarchie infinie de langages vérifiable, Rev. française automat. informat. recherche opérationnelle Sér, R-19, 5-20, (1975) · Zbl 0352.68088
[28] Siromoney, R., Finite-turn checking automata, J. comput. system sci., 5, 549-559, (1971) · Zbl 0231.68032
[29] Siromoney, R., On equal matrix languages, Information and control, 14, 135-151, (1969) · Zbl 0169.31402
[30] Sudborough, I.H., A note on tape-bounded complexity classes and linear context-free languages, J. assoc. comput. Mach., 22, 499-500, (1975) · Zbl 0318.68048
[31] Walljasper, S.J., Left-derivation bounded languages, J. comput. system sci., 8, 1-7, (1974) · Zbl 0281.68039
[32] Arora, A.; Sudborough, I.H., On languages log-tape reducible to context-free languages, Baltimore, MD, Proc. 1976 conf. information sci. systems, 27-32, (April 1976)
[33] R. Book, Simple representations of certain classes of languages, J. Assoc. Comput. Mach. (to appear). · Zbl 0364.68073
[34] Cook, S., Path systems and language recognition, Proc. 2nd ann. ACM symp. theory comput., 70-72, (May 1970), Northampton, MA
[35] Erni, W., Some further languages log-tape reducible to context-free languages, (), also Ph.D. dissertation, Universität Karlsruhe
[36] Ginsburg, S.; Goldstine, J.; Greibach, S., Uniformly erasable AFL, J. comput. system sci., 10, 165-182, (1975) · Zbl 0325.68042
[37] Ibarra, O.H., Controlled pushdown automata, Information sci., 6, 327-342, (1973) · Zbl 0278.68047
[38] Khabbaz, N.A., Control sets on linear grammars, Information and control, 25, 206-221, (1974) · Zbl 0298.68059
[39] Khabbaz, N.A., A geometrical hierarchy of languages, J. comput. system sci., 8, 142-157, (1974) · Zbl 0294.68029
[40] Klingenstein, F., Structures of bounded languages in certain families of languages, ()
[41] I.H. Sudborough, On the complexity of the membership problem for some extensions of context- free languages, Int. J. Comput. Math. (to appear). · Zbl 0398.68037
[42] K’el, D.I., Two-way a-transducers and AFL, J. comput. system sci., 10, 88-109, (1975) · Zbl 0303.68048
[43] J. Engelfriet, E.M. Schmidt and J. van Leewen, Stack machines and classes of nonnested maero- languages, Technical report. · Zbl 0428.68087
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.