×
Bédard, François; Lemieux, François; McKenzie, Pierre

Extensions to Barrington’s M-program model. (English) Zbl 0764.68040

Theor. Comput. Sci. 107, No. 1, 31-61 (1993).
Summary: Barrington’s “polynomial-length program over a monoid” is a model of computation which has been studied intensively in connection with the structure of the complexity class \(NC^ 1\) D. A. Barrington [J. Comput. Syst. Sci. 38, No. 1, 150-164 (1989; Zbl 0667.68059)]; D. A. Barrington and D. Therien [J. Assoc. Comput. Mach. 35, No. 4, 942- 952 (1988; Zbl 0667.68068); Lect. Notes Comput. Sci. 267, 163-173 (1987; Zbl 0634.68054)]; P. McKenzie and D. Therien [Lect. Notes Comput. Sci. 372, 589-602 (1989; Zbl 0682.68074)]; P. Péladeau [Classes of boolean circuits and varieties of finite monoids, LITP Tech. Report 89-25, Université Paris 7 (1989)]. Here two extensions of the model are considered. First, with the use of nonassociative structure (hence, groupoids) instead of (associative) monoids, polynomial-length program characterizations of complexity classes \(TC^ 0\), \(NL\), and LOGCFL, as well as new characterizations of \(\text{NC}^ 1\), are given. New “word problems” complete for LOGCFL, for NL and for \(\text{NC}^ 1\) under DLOGTIME-reductions are obtained as corollaries. Second, using monoids but permitting the use of a different monoid to handle each input length, new complexity classes are defined. Combinatorial arguments are then developed to resolve the relationship between various such classes defined in terms of polynomial-length programs over growing abelian monoid sequences. Then the orders of growing abelian group and monoid sequences required to accept specific languages defined in terms of the presence of a given substring are investigated. Finally, the two extensions are combined to obtain characterizations of L and NL in terms of polynomial-length programs defined over polynomially growing groupoid sequences. It is further argued that such programs are generally no more powerful than LOGCFL.

Cited in 1 Review
Cited in 12 Documents

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q05 Models of computation (Turing machines, etc.) (MSC2010)

Keywords:

polynomial-length programs; growing abelian monoid sequences; polynomially growing groupoid sequences

Citations:

Zbl 0667.68059; Zbl 0667.68068; Zbl 0634.68054; Zbl 0682.68074
Cite Review PDF
Full Text: DOI

References:

[1] R. Anderson and D.A.M. Barrington, private communication, 1989.; R. Anderson and D.A.M. Barrington, private communication, 1989.
[2] Barrington, D. A., Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^1\), (Proc. 18th ACM Symp. on the Theory of Computing (1986)). (Proc. 18th ACM Symp. on the Theory of Computing (1986)), J. Comput. System Sci., 38, 1, 150-164 (1989) · Zbl 0667.68059
[3] Mix Barrington, D.; Immerman, N.; Straubing, H., On uniformity within \(NC^1\), (Proc. 3rd Ann. Conf. on the Structure in Complexity Theory (1988), IEEE Computer Society Press). (Proc. 3rd Ann. Conf. on the Structure in Complexity Theory (1988), IEEE Computer Society Press), J. Comput. System Sci., 41, 3, 274-306 (1990) · Zbl 0719.68023
[4] D.A. Barrington, H. Straubing and D. Thérien, Non-uniform automata over groups, Inform. and Comput., in press.; D.A. Barrington, H. Straubing and D. Thérien, Non-uniform automata over groups, Inform. and Comput., in press. · Zbl 0727.68070
[5] Barrington, D.; Thérien, D., Finite monoids and the fine structure of \(NC^1\), J. Assoc. Comput. Mach., 35, 4, 941-952 (1988) · Zbl 0667.68068
[6] Borodin, A.; Dolev, D.; Fich, F.; Paul, W., Bounds for width-two branching programs, (Proc. 15th ACM Symp. on the Theory of Computing (1983)), 87-93
[7] Buss, S. R., The boolean formula value problem in ALOGTIME, (Proc. 19th ACM Symp. on the Theory of Computing (1987)), 123-131
[8] Buss, S. R.; Cook, S.; Gupta, A.; Ramachandran, V., An optimal parallel algorithm for formula evaluation (1989), SIAM J. Comput. to appear
[9] Chandra, A.; Furst, M.; Lipton, R., Multi-party protocols, (Proc. 15th ACM Symp. on the Theory of Computing (1983)), 94-99
[10] Chandra, A.; Stockmeyer, L.; Vishkin, U., Constant depth reducibility, SIAM J. Comput., 13, 2, 423-439 (1984) · Zbl 0538.68038
[11] Cobham, A., The recognition problem for the set of perfect squares, (Research Paper RC-1704 (1966), IBM Watson Research Center: IBM Watson Research Center Yorktown Heights, NY)
[12] Cook, S. A., A taxonomy of problems with fast parallel algorithms, Inform. and Comput., 64, 2-22 (1985) · Zbl 0575.68045
[13] Cook, S. A.; McKenzie, P., Problems complete for deterministic logarithmic space, J. Algorithms, 8, 385-394 (1987) · Zbl 0644.68058
[14] Furst, M. L.; Saxe, J. B.; Sipser, M., Parity, circuits, and the polynomial-time hierarchy, (Proc. 22nd IEEE Symp. on the Foundations of Computer Science (1981)). (Proc. 22nd IEEE Symp. on the Foundations of Computer Science (1981)), Math. Systems Theory, 17, 13-27 (1984) · Zbl 0534.94008
[15] Greibach, S., The hardest context-free language, SIAM J. Comput., 2, 4, 304-310 (1973) · Zbl 0278.68073
[16] Harrison, M. A., Introduction of Formal Language Theory (1978), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0411.68058
[17] Herstein, I., Topics in Algebra, ((1975), Wiley: Wiley New York) · Zbl 0122.01301
[18] Hopcroft, J. E.; Ullman, J. D., Introduction of Automata Theory, Languages, and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701
[19] Immerman, N.; Landau, S., The complexity of iterated multiplication, (Proc. 4th Ann. Conf. on the Structure of Complexity Theory (1989), IEEE Computer Society Press), 104-111
[20] Karp, R.; Lipton, R., Turing machines that take advice, Enseign. Math., 28, 191-209 (1982) · Zbl 0529.68025
[21] A. Klapper and L. Longpré, private communication, 1988.; A. Klapper and L. Longpré, private communication, 1988.
[22] McKenzie, P.; Péladeau, P.; Thérien, \(NC^1\): the automata-theoretic viewpoint, Computational Complexity, 1, 330-359 (1991) · Zbl 0774.68048
[23] McKenzie, P.; Thérien, D., Automata theory meets circuit complexity, (Proc. 16th Internat. Coll. on Automata, Languages and Programming. Proc. 16th Internat. Coll. on Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 372 (1989), Springer: Springer Berlin), 589-602 · Zbl 0682.68074
[24] Parberry, I.; Schnitger, G., Parallel computation with threshold functions, (Proc. 1st Structure in Complexity Theory Conf.. Proc. 1st Structure in Complexity Theory Conf., Lecture Notes in Computer Science, Vol. 223 (1986), Springer: Springer Berlin). (Proc. 1st Structure in Complexity Theory Conf.. Proc. 1st Structure in Complexity Theory Conf., Lecture Notes in Computer Science, Vol. 223 (1986), Springer: Springer Berlin), J. Comput. System Sci., 36, 3, 278-302 (1988) · Zbl 0652.68064
[25] Péladeau, P., Classes of boolean circuits and varieties of finite monoids, (LITP Tech. Report 89-25 (1989), Université Paris 7)
[26] Pin, J.-E., Varieties of Formal Languages (1986), Plenum: Plenum New York · Zbl 0632.68069
[27] Pippenger, N., On simultaneous resource bounds, (Proc. 20th IEEE Symp. on the Foundations of Computer Science (1979)), 307-311
[28] Pippenger, N.; Fischer, M. J., Relations among complexity measures, J. Assoc. Comput. Mach., 26, 2, 361-381 (1979) · Zbl 0405.68041
[29] Ruzzo, W. L., Tree-size bounded alternation, J. Comput. System Sci., 21, 218-235 (1980) · Zbl 0445.68034
[30] Ruzzo, W. L., On uniform circuit complexity, J. Comput. System Sci., 22, 3, 365-383 (1981) · Zbl 0462.68013
[31] Sudburough, I. H., A note on tape-bounded complexity classes and linear context-free languages, J. ACM, 22, 4, 499-500 (1975) · Zbl 0318.68048
[32] Sudburough, I., On the tape complexity of deterministic context-free languages, J. ACM, 25, 3, 405-414 (1978) · Zbl 0379.68054
[33] Thérien, D.; Péladeau, P., Sur les Langages Reconnus par des Groupes Nilpotents, (Comptesrendus de l’Académie des Sciences de Paris (1988)), 93-95, t. 306, Série I · Zbl 0638.68073
[34] Valiant, L. G., General context-free recognition in less than cubic time, J. Comput. System Sci., 10, 2, 308-315 (1975) · Zbl 0312.68042
[35] Venkateswaran, H., Properties that characterize LOGCFL, (Proc. 19th ACM Symp. on the Theory of Computing (1987)), 141-150 · Zbl 0776.68046
[36] Wegener, I., The Complexity of Boolean Functions (1987), Wiley: Wiley New York · Zbl 0623.94018
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.