State complexity of deterministic Watson–Crick automata and time varying Watson–Crick automata

被引：0
作者：
Kumar Sankar Ray
Kingshuk Chatterjee
Debayan Ganguly
机构：
[1] Indian Statistical Institute,Electronics and Communication Sciences Unit
来源：
Natural Computing | 2015年 / 14卷
关键词：
Non-deterministic Watson–Crick automata; Deterministic Watson–Crick automata; Time varying Watson–Crick automata; State complexity;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
Watson–Crick automata are finite automata working on double strands. Extensive research work has already been done on non-deterministic Watson–Crick automata and on deterministic Watson–Crick automata. State complexity of Watson–Crick automata has also been discussed. In this paper we analyze the state complexity of deterministic Watson–Crick automata with respect to non-deterministic block automata and non-deterministic finite automata. We also introduce new finite automata combining the properties of Watson–Crick automata and time varying automata. These automata have the unique property that the 1-limited stateless variant of these automata have the power to count. We further discuss the state complexity of time varying automata and time varying Watson–Crick automata.
引用
收藏
页码：691 / 699
页数：8
相关论文
共 18 条
[1]  
Czeizler E(2006)On the power of parallel communicating Watson–Crick automata systems Theor Comput Sci 358 142-147
[2]  
Czeizler E(2006)A short survey on Watson-Crick automata Bull EATCS 88 104-119
[3]  
Czeizler E(2009)On the descriptional complexity of Watson-Crick automata Theor Comput Sci 410 3250-3260
[4]  
Czeizler E(1986)Time varying finite automata Int J Comput Math 19 103-123
[5]  
Czeizler E(1999)State and transition complexity of Watson-Crick finite automata Fundam Comput Theory Lect Notes Comput Sci 1684 409-420
[6]  
Czeizler E(2013)Equivalence of subclasses of two-way non-deterministic Watson-Crick automata Appl Math 4 26-328
[7]  
Kari L(1994)The state complexities of some basic operations on regular languages Theor Comput Sci 125 315-undefined
[8]  
Salomaa K(undefined)undefined undefined undefined undefined-undefined
[9]  
Krithivasan K(undefined)undefined undefined undefined undefined-undefined
[10]  
Das A(undefined)undefined undefined undefined undefined-undefined
12