Nonerasing, Counting, and Majority over the Linear Time Hierarchy |
| |
| Authors: | Arnaud Durand Malika More |
| |
| Affiliation: | LACL, Département Informatique, Université Paris XII, 61 avenue du général de Gaulle, Créteil Cedex, 94010, Francef1;LLAIC, IUT Département Informatique, Université d'Auvergne, BP 86, Campus des Cézeaux, Aubière Cedex, 63172, France, f2 |
| |
| Abstract: | In this paper, we investigate several extensions of the linear time hierarchy (denoted by LTH). We first prove that it is not necessary to erase the oracle tape between two successive oracle calls, thereby lifting a common restriction on LTH machines. We also define a natural counting extension of LTH and show that it corresponds to a robust notion of counting bounded arithmetic predicates. Finally, we show that the computational power of the majority operator is equivalent to that of the exact counting operator in both contexts. |
| |
| Keywords: | Abbreviations: computational and structural complexityAbbreviations: logic in computer scienceAbbreviations: rudimentary relationsAbbreviations: counting classes |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
