Name
Abstract | ||
|---|---|---|
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. |
Year | Venue | Keywords |
|---|---|---|
2018 | Lobachevskii Journal of Mathematics | Two-way nonuniform automaton, size hierarchy, deterministic and nondeterministic models, probabilistic computation |
Field | DocType | Volume |
Discrete mathematics,Nondeterministic algorithm,Automaton,Witness,Probabilistic logic,Hierarchy,Transition function,Mathematics,Computation | Journal | abs/1801.10483 |
Citations | PageRank | References |
0 | 0.34 | 17 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kamil Khadiev | 1 | 26 | 7.92 |
| Rishat Ibrahimov | 2 | 0 | 0.34 |
| Abuzer Yakaryilmaz | 3 | 168 | 25.31 |