Characterizing NC with tier 0 pointers

Mathematical Logic Quarterly 50 (1):9-17 (2004)
  Copy   BIBTEX

Abstract

A two‐sorted term system characterizing NC implicitly is described. The term system is defined over the tree algebra ????, the free algebra generated by 0, 1 and ∗︁, and the recursion scheme uses pointers over tier 0. This differs from previous characterizations of NC, where tier 1 pointers were used or full parameter substitution over tier 0 was allowed. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)

Categories

Add categories

Keywords

Reprint years

DOI

10.1002/malq.200310070

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,991

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Characterizing NC with tier 0 pointers.Isabel Oitavem - 2004 - Mathematical Logic Quarterly 50 (1):9.
Characterizing PSPACE with pointers.Isabel Oitavern - 2008 - Mathematical Logic Quarterly 54 (3):323-329.
Characterizing PSPACE with pointers.Isabel Oitavem - 2008 - Mathematical Logic Quarterly 54 (3):323-329.
A note on parameter free Π1 -induction and restricted exponentiation.A. Cordón-Franco, A. Fernández-Margarit & F. F. Lara-Martín - 2011 - Mathematical Logic Quarterly 57 (5):444-455.
The minimal complementation property above 0′.Andrew E. M. Lewis - 2005 - Mathematical Logic Quarterly 51 (5):470-492.
λ-Definability on free algebras.Marek Zaionc - 1991 - Annals of Pure and Applied Logic 51 (3):279-300.
sigma-short Boolcan algebras.Makoto Takahashi & Yasuo Yoshinobu - 2003 - Mathematical Logic Quarterly 49 (6):543.
A topology induced by uniformity on BL-algebras.Masoud Haveshki, Esfandiar Eslami & Arsham Borumand Saeid - 2007 - Mathematical Logic Quarterly 53 (2):162-169.
The strong partition relation on ω 1 revisited.Steve Jackson & Russell May - 2004 - Mathematical Logic Quarterly 50 (1):33-40.
Notes on Craig interpolation for LJ with strong negation.Norihiro Kamide - 2011 - Mathematical Logic Quarterly 57 (4):395-399.

Analytics

Added to PP
2017-02-17

Downloads
3 (#1,727,010)

6 months
1 (#1,514,069)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Characterizing PSPACE with pointers.Isabel Oitavem - 2008 - Mathematical Logic Quarterly 54 (3):323-329.
A recursion-theoretic approach to NP.Isabel Oitavem - 2011 - Annals of Pure and Applied Logic 162 (8):661-666.

Add more citations

References found in this work

No references found.

Add more references