Bounded monotone recursion and multihead automata

被引：0
作者：
S. S. Marchenkov
机构：
[1] Moscow State University,Faculty of Computation Mathematics and Cybernetics
来源：
Programming and Computer Software | 2013年 / 39卷
关键词：
Turing Machine; Recursive Function; Word Function; Input Tape; Recursive Program;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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
页数：7
相关论文
共 3 条
  • [1] Volkov SA(2010)On the class of Skolem elementary functions J. Appl. Industrial Math. 4 588-599
  • [2] Volkov SA(2007)An exponential extension of the class of Skolem elementary functions and bounded superpositions of simple arithmetic functions Matematicheskie voprosy kibernetiki 16 163-190
  • [3] Marchenkov SS(1969)Elimination of recursion schemas in the Grzegorczyk [inline-graphic not available: see fulltext] class Math. Notes 5 561-568
1