О синтаксическом определении класса языков, распознаваемых недетерминированными машинами Тьюринга на логарифмической памяти
https://doi.org/10.15514/ISPRAS-2014-26(2)-13
Аннотация
Список литературы
1. Cook S.A. Variations on push-down machines In Proc. 1st ACM Symp. on Theory of Computing, pp. 229-232, 1969.
2. Cook S.A. Characterizations of push-down machines in terms of time-bounded computers Journal of the ACM, 18(1), pp. 4-18, 1971.
3. Cook S.A. Senti R. Storage requirements for deterministic polynomial time recognizable languages Journal of Computer and System Sciences, 13(1), pp. 25-37, 1976.
4. Immerman N. Nondeterministic space is closed under complementation, SIAM Journal on Computing 17, pp. 935-938, 1988.
5. Savitch W.J. Relationships between nondeterministic and deterministic tape complexities, Journal of Computer and System Sciences 4 (2), pp. 177-192, 1970.
6. Papadimitriou C. Computational Complexity. Boston: Addison-Wesley. ISBN 0-201-53082-1, 1994.
7. Arora S., Barak B. Computational complexity. A modern approach. Cambridge University Press. ISBN 978-0-521-42426-4, 2009.
8. Столбоушкин А.П., Тайцлин М.А. Динамические логики. Кибернетика и вычислительная техника под ред. В.А. Мельникова, том 2, Наука, Москва, стр. 180-230, 1986.
9. Stolboushkin A.P., Taitslin M.A. Dinamicheskie logiki. [Dynamic logics] Kibernetika i vychislitel'naya tekhnika [Cybernetics and computer technology] V.A. Melnikov (editor). Moscow, Nauka, pp. 180-230, 1986 (in Russian)
Рецензия
Для цитирования:
Носов Д.А. О синтаксическом определении класса языков, распознаваемых недетерминированными машинами Тьюринга на логарифмической памяти. Труды Института системного программирования РАН. 2014;26(2):275-296. https://doi.org/10.15514/ISPRAS-2014-26(2)-13
For citation:
Nosov D.A. Syntactical characterization of nondeterministic logspace complexity class. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2014;26(2):275-296. (In Russ.) https://doi.org/10.15514/ISPRAS-2014-26(2)-13