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 等数据库收录！

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