Standard

Совместные ограничения сверху зоны и времени для взаимного моделирования машин Тьюринга и алгоритмов Маркова — Поста. / Косовский, Н.К.; Косовская, Т.М.; Косовский, Н.Н.

In: ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. СЕРИЯ 1: МАТЕМАТИКА, МЕХАНИКА, АСТРОНОМИЯ, No. 2, 2015, p. 191-194.

Research output: Contribution to journal › Article › peer-review

Harvard

Косовский, НК, Косовская, ТМ & Косовский, НН 2015, 'Совместные ограничения сверху зоны и времени для взаимного моделирования машин Тьюринга и алгоритмов Маркова — Поста', ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. СЕРИЯ 1: МАТЕМАТИКА, МЕХАНИКА, АСТРОНОМИЯ, no. 2, pp. 191-194.

APA

Косовский, Н. К., Косовская, Т. М., & Косовский, Н. Н. (2015). Совместные ограничения сверху зоны и времени для взаимного моделирования машин Тьюринга и алгоритмов Маркова — Поста. ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. СЕРИЯ 1: МАТЕМАТИКА, МЕХАНИКА, АСТРОНОМИЯ, (2), 191-194.

Vancouver

Косовский НК, Косовская ТМ, Косовский НН. Совместные ограничения сверху зоны и времени для взаимного моделирования машин Тьюринга и алгоритмов Маркова — Поста. ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. СЕРИЯ 1: МАТЕМАТИКА, МЕХАНИКА, АСТРОНОМИЯ. 2015;(2):191-194.

Author

Косовский, Н.К. ; Косовская, Т.М. ; Косовский, Н.Н. / Совместные ограничения сверху зоны и времени для взаимного моделирования машин Тьюринга и алгоритмов Маркова — Поста. In: ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. СЕРИЯ 1: МАТЕМАТИКА, МЕХАНИКА, АСТРОНОМИЯ. 2015 ; No. 2. pp. 191-194.

BibTeX

@article{cb3b0fe461664b15855e66327e763625,
title = "Совместные ограничения сверху зоны и времени для взаимного моделирования машин Тьюринга и алгоритмов Маркова — Поста",
abstract = "В качестве сложностной характеристики алгоритма рассматривается его совместная ограниченность по времени и по зоне. Для совместно ограниченные сверху по времени и по зоне алгоритмов Маркова -- Поста и совместно ограниченные сверху по времени и по зоне многоленточных машин Тьюринга доказана их взаимозаменяемость с точностью до линейной функции по зоне и полинома по времени машины Тьюринга соответственно при доказательстве сложностных характеристик алгоритмов. При этом используются не более чем двухбуквенные расширения внешнего алфавита. Доказаны теоремы.",
keywords = "машина Тьюринга, алгоритм Маркова -- Поста, временная и зональная сложность алгоритмов, совместные верхние ограничения сложности",
author = "Н.К. Косовский and Т.М. Косовская and Н.Н. Косовский",
year = "2015",
language = "русский",
pages = "191--194",
journal = "ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ",
issn = "1025-3106",
publisher = "Издательство Санкт-Петербургского университета",
number = "2",

}

RIS

TY - JOUR

T1 - Совместные ограничения сверху зоны и времени для взаимного моделирования машин Тьюринга и алгоритмов Маркова — Поста

AU - Косовский, Н.К.

AU - Косовская, Т.М.

AU - Косовский, Н.Н.

PY - 2015

Y1 - 2015

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

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

KW - машина Тьюринга

KW - алгоритм Маркова -- Поста

KW - временная и зональная сложность алгоритмов

KW - совместные верхние ограничения сложности

M3 - статья

SP - 191

EP - 194

JO - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ

JF - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ

SN - 1025-3106

IS - 2

ER -

ID: 5772831