Between SC and LOGDCFL: families of languages accepted by logarithmic-space deterministic auxiliary depth-k storage automata

References

• B. Braunmühl, S. Cook, K. Mehlhorn, and R. Verbeek, The recognition of determinsitic CFLs in small time and space, Inf. Control 56 (1983), pp. 34–51.
   Google Scholar
• T. Chan, Pushdown automata with reversal-bounded counters, J. Comput. Syst. Sci. 37 (1988), pp. 269–291.
   Web of Science ®Google Scholar
• S.A. Cook, Characterizations of pushdown machines in terms of time-bounded computers, J. ACM 18 (1971), pp. 4–18.
   Web of Science ®Google Scholar
• S.A. Cook, Determinsitic CFLs are accepted simultaneously in polynomial time and log squared space, in The Proceedings of the 11th Annual ACM Symposium on Theory of Computing (STOC'79), 1979, pp. 338–345.
   Google Scholar
• P. Dymond and W. Ruzzo, Parallel RAMs with owned global memory and deterministic context-free language recognition, in The Proceedings of the 13th International Colloquium on Automata, Languages and Programming (ICALP'86), Lecture Notes in Computer Science Vol. 226, Springer, 1986, pp. 95–104.
   Google Scholar
• H. Fernau, K.J. Lange, and K. Reinhardt, Advocating owership, in The Proceedings of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS'96), Lecture Notes in Computer Science Vol. 1180, Springer, 1996, pp.286–297.
   Google Scholar
• Z. Galil, Some open problems in the theory of computation as questions about two-way determinsitic pushdown automaton languages, Math. Syst. Theory 10 (1977), pp. 211–228.
   Google Scholar
• S. Ginsburg and S. Greibach, Deterministic context free languages, Inf. Control 9 (1966), pp. 620–648.
   Google Scholar
• S. Ginsburg, S.A. Greibach, and M.A. Harrison, Stack automata and compiling, J. ACM 14 (1967), pp. 172–201.
   Web of Science ®Google Scholar
• S. Ginsburg, S.A. Greibach, and M.A. Harrison, One-way stack automata, J. ACM 14 (1967), pp. 389–418.
   Web of Science ®Google Scholar
• J. Hartmanis, On non-determinacy in simple computing devices, Acta Inf. 1 (1972), pp. 336–344.
   Google Scholar
• T.N. Hibbard, A generalization of context-free determinism, Inf. Control 11 (1967), pp. 196–238.
   Google Scholar
• O.H. Ibarra, Characterizations of some tapes and time complexity classes of Tuirng machines in terms of multihead and auxiliary stack automata, J. Comput. Syst. Sci. 5 (1971), pp. 88–117.
   Google Scholar
• M. Kutrib, G. Pighizzini, and M. Wendlandt, Descriptiopnal complexity of limited automata, Inf. Comput. 259 (2018), pp. 259–276.
   Web of Science ®Google Scholar
• M. Kutrib and M. Wendlandt, Reversible limited automata, Fund. Inf. 155 (2017), pp. 31–58.
   Web of Science ®Google Scholar
• L.Y. Liu and P. Weiner, An infinite hierarchy of intersections of context-free langauges, Math. Syst. Theory 7 (1973), pp. 185–192.
   Google Scholar
• M. Lohrey, Decidability and complexity in automatic monoids, Int. Found. Comput. Sci. 16 (2005), pp. 707–722.
   Web of Science ®Google Scholar
• P. McKenzie, K. Reinhardt, and V. Vinay, Circuits and context-free languages, in The Proceedings of the 5th Annual International Computing and Combinatorics Conference (COCOON'99), Lecture Notes in Computer Science, Springer, vol. 1627, 1999, pp. 194–203.
   Google Scholar
• A. Meduna, Deep pushdown automata, Acta Inf. 42 (2006), pp. 541–552.
   Web of Science ®Google Scholar
• G. Pighizzini and A. Pisoni, Limited automata and regular languages, Int. J. Found. Comput. Sci. 25 (2014), pp. 897–916.
   Web of Science ®Google Scholar
• G. Pighizzini and A. Pisoni, Limited automata and context-free languages, Fund. Inf. 136 (2015), pp. 157–176.
   Web of Science ®Google Scholar
• G. Pighizzini and L. Prigioniero, Limited automata and unary languages, Inf. Comput. 266 (2019), pp. 60–74.
   Web of Science ®Google Scholar
• I.H. Sudborough, On the tape complexity of determinsitic context-free languages, J. ACM 25 (1978), pp. 405–414.
   Web of Science ®Google Scholar
• K. Tadaki, T. Yamakami, and J.C.H. Lin, Theory of one-tape linear-time Turing machinesTheor. Comput. Sci. 411 (2010), pp. 22–43. An extended abstract appeared in the Proc. of the 30th SOFSEM Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2004), Lecture Notes in Computer Science, Springer, vol. 2932, 2004, pp. 335–348.
   Web of Science ®Google Scholar
• T. Yamakami, Behavioral strengths and weaknesses of various models of limited automata, in The Proceeding of the 45th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2019), Lecture Notes in Computer Science Vol. 11376, Springer, 2019, pp. 519–530. A complete and corrected version is available at arXiv:2111.05000, 2021.
   Google Scholar
• T. Yamakami, Intersection and union hierarchies of deterministic context-free languages and pumping lemmas, in The Proceedings of the 15th International Conference on Language and Automata Theory and Applications (LATA 2020). Lecture Notes in Computer Science Vol. 12038, Springer, 2020, pp. 341–353. A complete and corrected version is available at arXiv:2112.09383, 2021.
   Google Scholar