A characterization of alternating log time by ramified recurrence
| Autor: | Daniel Leivant, Jean-Yves Marion |
|---|---|
| Přispěvatelé: | Department of Computer Science [Santa Barbara], University of California [Santa Barbara] (UC Santa Barbara), University of California (UC)-University of California (UC), Linear logic, proof networks and categorial grammars (CALLIGRAMME), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), University of California [Santa Barbara] (UCSB), University of California-University of California |
| Jazyk: | angličtina |
| Rok vydání: | 2000 |
| Předmět: |
Polynomial
General Computer Science Logarithm Computational complexity theory [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH] Ramified recursion 0102 computer and information sciences 02 engineering and technology 01 natural sciences Theoretical Computer Science Combinatorics Bounding overwatch 0202 electrical engineering electronic engineering information engineering Bitwise operation Mathematics Discrete mathematics Implicit computational complexity Binary tree Tree recursion Recursion with substitution parameters complexité de récursion Recursion (computer science) Tree (graph theory) recursion complexity Alternation Alogtime 010201 computation theory & mathematics 020201 artificial intelligence & image processing Computer Science(all) |
| Zdroj: | Theoretical Computer Science Theoretical Computer Science, 2000, 236 (1-2), pp.192-208. ⟨10.1016/S0304-3975(99)00209-1⟩ Theoretical Computer Science, Elsevier, 2000, 236 (1-2), pp.192-208. ⟨10.1016/S0304-3975(99)00209-1⟩ |
| ISSN: | 1879-2294 0304-3975 |
| DOI: | 10.1016/S0304-3975(99)00209-1⟩ |
| Popis: | We give a machine-independent characterization of the class of functions bitwise computable in alternating logarithmic time, with output of polynomial size. Recall that ALogTime is the same, for decision problems, as the U E ∗ -uniform variant of NC 1 Ruzzo, J. Comput. System Sci. 22 (1981) 365–383. Our characterization is in terms of a weak form of ramified tree recurrence with substitutions. No initial functions other than basic tree operations are used, and no bounding conditions on the recurrence. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect