Preview

Труды Института системного программирования РАН

Расширенный поиск

О синтаксическом определении класса языков, распознаваемых недетерминированными машинами Тьюринга на логарифмической памяти

https://doi.org/10.15514/ISPRAS-2014-26(2)-13

Аннотация

В работе М. А. Тайцлина и А. П. Столбоушкина было введено понятие недетерминированной программы, и определен класс языков, распознаваемых недетерминированными программами. Доказана теорема, свидетельствующая о близости этого класса, и NL. Мы исследуем класс языков, определяемый в некоторой модификации указанной вычислительной модели, и доказываем, что рассматриваемый класс языков равен NL.

Об авторе

Д. А. Носов
ООО «Яндекс», Москва
Россия


Список литературы

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



Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)