200
Views
0
CrossRef citations to date
0
Altmetric
27th International Computing and Combinatorics Conference (Selected Papers from COCOON 2021)

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

Pages 1-31 | Received 31 Mar 2022, Accepted 12 Dec 2022, Published online: 03 Feb 2023

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.
  • T. Chan, Pushdown automata with reversal-bounded counters, J. Comput. Syst. Sci. 37 (1988), pp. 269–291.
  • S.A. Cook, Characterizations of pushdown machines in terms of time-bounded computers, J. ACM 18 (1971), pp. 4–18.
  • 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.
  • 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.
  • 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.
  • 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.
  • S. Ginsburg and S. Greibach, Deterministic context free languages, Inf. Control 9 (1966), pp. 620–648.
  • S. Ginsburg, S.A. Greibach, and M.A. Harrison, Stack automata and compiling, J. ACM 14 (1967), pp. 172–201.
  • S. Ginsburg, S.A. Greibach, and M.A. Harrison, One-way stack automata, J. ACM 14 (1967), pp. 389–418.
  • J. Hartmanis, On non-determinacy in simple computing devices, Acta Inf. 1 (1972), pp. 336–344.
  • T.N. Hibbard, A generalization of context-free determinism, Inf. Control 11 (1967), pp. 196–238.
  • 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.
  • M. Kutrib, G. Pighizzini, and M. Wendlandt, Descriptiopnal complexity of limited automata, Inf. Comput. 259 (2018), pp. 259–276.
  • M. Kutrib and M. Wendlandt, Reversible limited automata, Fund. Inf. 155 (2017), pp. 31–58.
  • L.Y. Liu and P. Weiner, An infinite hierarchy of intersections of context-free langauges, Math. Syst. Theory 7 (1973), pp. 185–192.
  • M. Lohrey, Decidability and complexity in automatic monoids, Int. Found. Comput. Sci. 16 (2005), pp. 707–722.
  • 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.
  • A. Meduna, Deep pushdown automata, Acta Inf. 42 (2006), pp. 541–552.
  • G. Pighizzini and A. Pisoni, Limited automata and regular languages, Int. J. Found. Comput. Sci. 25 (2014), pp. 897–916.
  • G. Pighizzini and A. Pisoni, Limited automata and context-free languages, Fund. Inf. 136 (2015), pp. 157–176.
  • G. Pighizzini and L. Prigioniero, Limited automata and unary languages, Inf. Comput. 266 (2019), pp. 60–74.
  • I.H. Sudborough, On the tape complexity of determinsitic context-free languages, J. ACM 25 (1978), pp. 405–414.
  • 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.
  • 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.
  • 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.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.