Two-way deterministic automata with two reversals are exponentially more succinct than with one reversal

被引：3
作者：
Balcerzak, Marcin [1 ]
Niwinski, Damian [1 ]
机构：
[1] Warsaw Univ, Fac Math Informat & Mech, Warsaw, Poland
来源：
INFORMATION PROCESSING LETTERS | 2010年 / 110卷 / 10期
关键词：
Formal languages; Regular languages; Two-way finite automata; Bounded number of reversals; FINITE AUTOMATA;
D O I：
10.1016/j.ipl.2010.03.008
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We prove that limiting the number of reversals from two to one can cause an exponential blow-up in the size of two-way deterministic automaton. (C) 2010 Elsevier B.V. All rights reserved.
引用
收藏
页码：396 / 398
页数：3
相关论文
共 7 条
[1]  
[Anonymous], 1979, INTRO AUTOMATA THEOR
[2]  
Hromkovic J, 2003, LECT NOTES COMPUT SC, V2719, P439
[3]  
HROMKOVIC J, 1985, ACTA INFORM, V22, P589
[4]   FINITE AUTOMATA AND THEIR DECISION PROBLEMS [J].
RABIN, MO ;
SCOTT, D .
IBM JOURNAL OF RESEARCH AND DEVELOPMENT, 1959, 3 (02) :114-125
[5]   THE REDUCTION OF 2-WAY AUTOMATA TO ONE-WAY AUTOMATA [J].
SHEPHERDSON, JC .
IBM JOURNAL OF RESEARCH AND DEVELOPMENT, 1959, 3 (02) :198-200
[6]  
SIPSER M, 1979, STOC 79, P360
[7]  
[No title captured]
1