期刊文献+
共找到1篇文章
< 1 >
每页显示 20 50 100
1-Way Multihead Quantum Finite State Automata
1
作者 Debayan Ganguly Kingshuk Chatterjee Kumar Sankar Ray 《Applied Mathematics》 2016年第9期1005-1022,共18页
1-way multihead quantum finite state automata (1QFA(k)) can be thought of modified version of 1-way quantum finite state automata (1QFA) and k-letter quantum finite state automata (k-letter QFA) respectively. It has b... 1-way multihead quantum finite state automata (1QFA(k)) can be thought of modified version of 1-way quantum finite state automata (1QFA) and k-letter quantum finite state automata (k-letter QFA) respectively. It has been shown by Moore and Crutchfield as well as Konadacs and Watrous that 1QFA can’t accept all regular language. In this paper, we show different language recognizing capabilities of our model 1-way multihead QFAs. New results presented in this paper are the following ones: 1) We show that newly introduced 1-way 2-head quantum finite state automaton (1QFA(2)) structure can accept all unary regular languages. 2) A language which can’t be accepted by 1-way deterministic 2-head finite state automaton (1DFA((2)) can be accepted by 1QFA(2) with bounded error. 3) 1QFA(2) is more powerful than 1-way reversible 2-head finite state automaton (1RMFA(2)) with respect to recognition of language. 展开更多
关键词 1-Way Quantum finite state automaton (1QFA) k-Letter Quantum finite state Automata (k-Letter QFA) 1-Way Multihead Quantum finite state automaton (1QFA(k)) 1-Way deterministic 2-Head finite state automaton (1DFA((2)) 1-Way Reversible Multihead finite state automaton (1RMFA(k))
下载PDF
上一页 1 下一页 到第
使用帮助 返回顶部