Nonerasing, Counting, and Majority over the Linear Time Hierarchy
| Autor: | Arnaud Durand, Malika More |
|---|---|
| Rok vydání: | 2002 |
| Předmět: |
Discrete mathematics
Hierarchy (mathematics) Logic in computer science Computational complexity theory Extension (predicate logic) Oracle Theoretical Computer Science Computer Science Applications Turing machine symbols.namesake Operator (computer programming) Computational Theory and Mathematics symbols Time complexity Mathematics Information Systems |
| Zdroj: | Information and Computation. 174(2):132-142 |
| ISSN: | 0890-5401 |
| DOI: | 10.1006/inco.2001.3084 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect