New Size Hierarchies for Two Way Automata
- 作者: Ibrahimov R.1, Khadiev K.1,2, Yakaryılmaz A.2
-
隶属关系:
- Institute of Computational Mathematics and Information Technologies
- Center for Quantum Computer Science, Faculty of Computing
- 期: 卷 39, 编号 7 (2018)
- 页面: 997-1009
- 栏目: Article
- URL: https://journals.rcsi.science/1995-0802/article/view/202813
- DOI: https://doi.org/10.1134/S1995080218070120
- ID: 202813
如何引用文章
详细
We introduce a new type of nonuniform two-way automaton that can use a different transition function for each tape square. We also enhance this model by allowing to shuffle the given input at the beginning of the computation. Then we present some hierarchy and incomparability results on the number of states for the types of deterministic, nondeterministic, and bounded-error probabilistic models. For this purpose, we provide some lower bounds for all three models based on the numbers of subfunctions and we define two witness functions.
作者简介
R. Ibrahimov
Institute of Computational Mathematics and Information Technologies
编辑信件的主要联系方式.
Email: rishat.ibrahimov@yandex.ru
俄罗斯联邦, ul. Kremlevskaya 35, Kazan, Tatarstan, 420008
K. Khadiev
Institute of Computational Mathematics and Information Technologies; Center for Quantum Computer Science, Faculty of Computing
Email: rishat.ibrahimov@yandex.ru
俄罗斯联邦, ul. Kremlevskaya 35, Kazan, Tatarstan, 420008; Raina bulv. 19, Riga, LV-1586
A. Yakaryılmaz
Center for Quantum Computer Science, Faculty of Computing
Email: rishat.ibrahimov@yandex.ru
拉脱维亚, Raina bulv. 19, Riga, LV-1586
![](/img/style/loading.gif)