# zbMATH — the first resource for mathematics

An algebra and a logic for $$NC^ 1$$. (English) Zbl 0717.68032
This paper, which appeared in an earlier version K. Compton and C. Laflamme [A logic and an Algebra for $$NC^ 1$$ in: Proc. 3rd Annual Conference on Logic in Computer Science, (1988; Washington (IEEE Computer Society Press)], presents an algebra and a logic characterizing the complexity class $$NC^ 1$$. In the algebraic characterization a recursion scheme called upward tree recursion is applied to a class of simple functions. In the logical characterization, first-order logic is augmented by an operator for defining relations by primitive recursion provided that every structure has a relation giving the binary representations of integers.
Reviewer: E.Heinrich

##### MSC:
 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.) 03D15 Complexity of computation (including implicit computational complexity) 03C99 Model theory
##### Keywords:
complexity class $$NC^ 1$$
Full Text:
##### References:
  Allen, B., Arithmetizing uniform NC, () · Zbl 0741.03019  Barrington, D.A., Bounded-width polynomial-size branching programs recognize exactly those languages in NC1, (), 1-5  Barrington, D.A.; Thérien, D., Finite monoids and the fine structure of NC1, (), 101-109  Barrington, D.A.M.; Immerman, N.; Straubing, H., On uniformity within NC1, (), 47-59  Bennett, J.H., On spectra, () · Zbl 0335.92014  Büchi, J.R., Weak second-order arithmetic and finite automata, Z. math. logik grundlag. math., 6, 66-92, (1960) · Zbl 0103.24705  Buss, S.R., Bounded arithmetic, () · Zbl 0654.03043  Clote, P., A first order theory for the parallel complexity class NC, Boston college computer science department technical report BCCS-89-01, (1989), Chestnut Hill, MA  Cobham, A., The intrinsic computational difficulty of functions, (), 24-30  Codd, E.F., Relational completeness of data base sublanguages, (), 65-98  Compton, K.; Laflamme, C., A logic and an algebra for NC1, ()  Cook, S.A., A taxonomy of problems with fast parallel algorithms, Inform. and control, 64, 2-22, (1985) · Zbl 0575.68045  Elgot, C.C., Decision problems of finite-automata design and related arithmetics, Trans. amer. math. soc., 98, 21-51, (1961) · Zbl 0111.01102  Fagin, R., Generalized first-order spectra and polynomial time recognizable sets, (), 43-73  Gurevich, Y., Algebras of feasible functions, (), 210-214  Immerman, N., Relational queries computable in polynomial time, Inform. and control, 68, 86-104, (1986) · Zbl 0612.68086  Immerman, N., Expressibility as a complexity measure: results and directions, (), 194-202  Immerman, N., Languages that capture complexity classes, SIAM J. comput., 16, 347-354, (1987) · Zbl 0634.68034  Lind, J., Computing in logarithmic space, ()  Lynch, J., Complexity classes and theories of finite models, Math. systems theory, 15, 127-144, (1989) · Zbl 0484.03020  Ritchie, R., Classes of predictably computable functions, Trans. amer. math. soc., 106, 139-173, (1963) · Zbl 0107.01001  Ruzzo, W., On uniform circuit complexity, J. comput. system sci., 22, 365-383, (1981) · Zbl 0462.68013  Vardi, M., Complexity of relational query languages, (), 137-146
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.