String matching algorithms play an important role in computer science. However, there is no uniform mathematical model to describe these algorithms. Thus, read-head-Skippable DFA (SDFA) is put forward, which is an ext...String matching algorithms play an important role in computer science. However, there is no uniform mathematical model to describe these algorithms. Thus, read-head-Skippable DFA (SDFA) is put forward, which is an extension of two-way DFA. It is proved that SDFA is equivalent to DFA. Furthermore, SDFA is a more natural mathematical model for string matching algorithms. After that, four types of the movement of the read head of string matching are analyzed and modeled by SDFA. Finally, the SDFA model of BMA string matching algorithms is given.展开更多
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.展开更多
基金中国高科技研究与发展项目，the Defence Pre-research Project of the Tenth Five-Year Plan of China
文摘String matching algorithms play an important role in computer science. However, there is no uniform mathematical model to describe these algorithms. Thus, read-head-Skippable DFA (SDFA) is put forward, which is an extension of two-way DFA. It is proved that SDFA is equivalent to DFA. Furthermore, SDFA is a more natural mathematical model for string matching algorithms. After that, four types of the movement of the read head of string matching are analyzed and modeled by SDFA. Finally, the SDFA model of BMA string matching algorithms is given.
文摘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.
