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

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
03D15 Complexity of computation (including implicit computational complexity)
03C99 Model theory
Full Text: DOI
[1] Allen, B., Arithmetizing uniform NC, () · Zbl 0741.03019
[2] Barrington, D.A., Bounded-width polynomial-size branching programs recognize exactly those languages in NC1, (), 1-5
[3] Barrington, D.A.; Thérien, D., Finite monoids and the fine structure of NC1, (), 101-109
[4] Barrington, D.A.M.; Immerman, N.; Straubing, H., On uniformity within NC1, (), 47-59
[5] Bennett, J.H., On spectra, () · Zbl 0335.92014
[6] Büchi, J.R., Weak second-order arithmetic and finite automata, Z. math. logik grundlag. math., 6, 66-92, (1960) · Zbl 0103.24705
[7] Buss, S.R., Bounded arithmetic, () · Zbl 0654.03043
[8] 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
[9] Cobham, A., The intrinsic computational difficulty of functions, (), 24-30
[10] Codd, E.F., Relational completeness of data base sublanguages, (), 65-98
[11] Compton, K.; Laflamme, C., A logic and an algebra for NC1, ()
[12] Cook, S.A., A taxonomy of problems with fast parallel algorithms, Inform. and control, 64, 2-22, (1985) · Zbl 0575.68045
[13] Elgot, C.C., Decision problems of finite-automata design and related arithmetics, Trans. amer. math. soc., 98, 21-51, (1961) · Zbl 0111.01102
[14] Fagin, R., Generalized first-order spectra and polynomial time recognizable sets, (), 43-73
[15] Gurevich, Y., Algebras of feasible functions, (), 210-214
[16] Immerman, N., Relational queries computable in polynomial time, Inform. and control, 68, 86-104, (1986) · Zbl 0612.68086
[17] Immerman, N., Expressibility as a complexity measure: results and directions, (), 194-202
[18] Immerman, N., Languages that capture complexity classes, SIAM J. comput., 16, 347-354, (1987) · Zbl 0634.68034
[19] Lind, J., Computing in logarithmic space, ()
[20] Lynch, J., Complexity classes and theories of finite models, Math. systems theory, 15, 127-144, (1989) · Zbl 0484.03020
[21] Ritchie, R., Classes of predictably computable functions, Trans. amer. math. soc., 106, 139-173, (1963) · Zbl 0107.01001
[22] Ruzzo, W., On uniform circuit complexity, J. comput. system sci., 22, 365-383, (1981) · Zbl 0462.68013
[23] 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.