One-way multihead finite automata and 2-bounded languages期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

首页 | 本学科首页

官方微博 | 高级检索

One-way multihead finite automata and 2-bounded languages

Authors:

Miros?aw Kuty?owski

Affiliation:

1. Institute of Computer Science, University of Wroc?aw, ul. Przesmyckiego 20, PL-51-151, Wroc?aw, Poland

Abstract:

LanguagesL _n={1^x2^ix:i, x isin

, 1

n} were used to show that, for eachk, one-way non-sensing deterministic finite automata (1-MFA) withk+1 heads are more powerful than such automata withk heads, even if we consider only 2-bounded languages (Chrobak). Fork isin

letf(k) be the maximal numbern such that languageL _n can be recognized by a 1-MFA withk heads. We present a precise inductive formula forf(k). It may be shown that, fork

$\frac{{(2k - 5)! \cdot (k - 2) \cdot (k - 1)}}{{2^{k - 3} }} \leqslant f(k) \leqslant \frac{{(2k - 5)! \cdot (k - 2) \cdot (k - 1) \cdot 3k^2 }}{{2^{k - 3} }}$

Keywords:
本文献已被 SpringerLink 等数据库收录！

设为首页 | 免责声明 | 关于勤云 | 加入收藏