Bounded monotone recursion and multihead automata

被引：0
|
作者：
Marchenkov, S. S. [1 ]
机构：
[1] Moscow MV Lomonosov State Univ, Fac Computat Math & Cybernet, Moscow 119991, Russia
来源：
PROGRAMMING AND COMPUTER SOFTWARE | 2013年 / 39卷 / 06期
基金：
俄罗斯基础研究基金会;
关键词：
Automata theory;
D O I：
10.1134/S0361768813060054
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
On the basis of bounded monotone recursion, a class BMR of word functions over the alphabet {1, 2} is defined. A new type of a computing device is introduced, which is called a multihead nonerasing automaton with output, or an MH automaton. It is proved that the class BMR coincides with the class MHA of word functions computable by MH automata in polynomial time. Numerous examples of word functions from the class BMR are given.
引用
收藏
页码：301 / 308
页数：8
相关论文
共 50 条
12345