Взаимное моделирование последовательных и параллельных словарных вычислений

Работа посвящена связи параллельных и последовательных вычислений. С одной стороны, рассматривается класс словарных предикатов, основанных на последовательных вычислениях, ограниченных по памяти константами и имеющих полиномиальную временную сложность. С другой стороны, рассматривается класс словарных предикатов, вычислимых на параллельных альтернирующих машинах за логарифмическое время. Доказано совпадение соответствующих классов. Предложено направление использования полученных результатов для взаимного преобразования и сочетания вычислений на молекулярных биоподобных последовательных машинах и параллельных вычислениях на векторно-матричных компьютерах. Предполагаемые области применения: обработка изображений в реальном масштабе времени для задач управления, анализ больших текстов и других больших данных.