The word and generator problems for lattices. (English) Zbl 0649.06003
Summary: We present polynomial-time algorithms for the uniform word problem and for the generator problem for lattices. The algorithms are derived from novel, proof-theoretic approaches. We prove that both problems are log- space complete for P, but can be solved in deterministic logarithmic space in the case of free lattices. We also show that the more general problem of testing whether a given open sentence is true in all lattices is co-NP complete.
MSC:
| 06B25 | Free lattices, projective lattices, word problems |
| 03D40 | Word problems, etc. in computability and recursion theory |
| 68Q25 | Analysis of algorithms and problem complexity |
Keywords:
polynomial-time algorithms; uniform word problem; generator problem; log- space complete for P; deterministic logarithmic space; free lattices; co- NP completeReferences:
| [1] | Birkhoff, G., (Lattice Theory (1967), Amer. Math. Soc: Amer. Math. Soc Providence, RI) · Zbl 0126.03801 |
| [2] | Bloniarz, P. A.; Hunt, H. B.; Rosenkrantz, D. J., Algebraic structures with hard equivalence and minimization problems, J. Assoc. Comput. Mach., 31, No. 4, 879-904 (1984) · Zbl 0628.68039 |
| [3] | Cosmadakis, S. S., Equational Theories and Database Constraints, (Ph.D. thesis (1985), Massachusetts Institute of Technology) |
| [4] | Cosmadakis, S. S.; Kanellakis, P. C.; Spyratos, N., Partition semantics for relations, (Proceedings, 4th ACM Symposium on Principles of Database Systems. Proceedings, 4th ACM Symposium on Principles of Database Systems, March, 1985 (1985)), 261-275 |
| [5] | Crawley, P.; Dilworth, R. P., (Algebraic Theory of Lattices (1973), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ) · Zbl 0494.06001 |
| [6] | Dean, R. A., Component subsets of the free lattice on \(n\) generators, (Proc. Amer. Math. Soc., 7 (1956)), 220-226 · Zbl 0071.25701 |
| [7] | Enderton, H. B., (A Mathematical Introduction to Logic (1972), Academic Press: Academic Press New York/London) · Zbl 0298.02002 |
| [8] | Evans, T., The word problem for abstract algebras, J. London Math. Soc., 26, 64-71 (1951) · Zbl 0042.03303 |
| [9] | Evans, T., Word problems, Bull. Amer. Math. Soc., 84, 789-802 (1978) · Zbl 0389.03018 |
| [10] | Freese, R., Free modular lattices, Trans. Amer. Math. Soc., 261, 81-91 (1980) · Zbl 0437.06006 |
| [11] | Garey, M. R.; Johnson, D. S., (Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco) · Zbl 0411.68039 |
| [12] | Goldschlager, L. M., The monotone and planar circuit value problems are logspace-complete for \(P\), SIGACT News, 9, No. 2, 25-29 (1977) · Zbl 0356.94042 |
| [13] | Grätzer, G., (Universal Algebra (1979), Springer-Verlag: Springer-Verlag New York) · Zbl 0412.08001 |
| [14] | Grzegorczyk, A., Undecidability of some topological theories, Fund. Math., 38, 137-152 (1951) · Zbl 0045.00301 |
| [15] | Hopcroft, J. E.; Ullman, J. D., (Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0426.68001 |
| [16] | Huet, G.; Oppen, D., Equations and rewrite rules: A survey, (Book, R., Formal Languages: Perspectives and Open Problems (1980), Academic Press: Academic Press New York/London), 349-403 |
| [17] | Hunt, H. B.; Rosenkrantz, D. J.; Bloniarz, P. A., (On the Computational Complexity of Algebra on Lattices 1 (1984), State University of New York at Albany), Report 84-4 · Zbl 0642.06005 |
| [18] | Jones, N. D.; Laaser, W. T., Complete problems for deterministic polynomial time, Theoret. Comput. Sci., 3, No. 2, 105-117 (1977) · Zbl 0352.68068 |
| [19] | Kozen, D., Complexity of finitely presented algebras, (Proceedings, 9th Sympos. Theory of Comput. 1977 (1977)) · Zbl 0824.68076 |
| [20] | Markov, A., On the impossibility of certain algorithms in the theory of associative systems, Dokl. Akad. Nauk SSSR (N.S.), 55, 583-586 (1947) · Zbl 0029.10101 |
| [21] | Mayr, E. W.; Meyer, A. R., The complexity of the word problems for commutative semigroups and polynomial ideals, Adv. in Math., 46, No. 3, 305-329 (1982) · Zbl 0506.03007 |
| [22] | McKinsey, J. C.C., The decision problem for some classes of sentences, J. Symbolic Logic, 8, 61-76 (1943) · Zbl 0063.03864 |
| [23] | Novikov, P. S., On the algorithmic unsolvability of the word problem in group theory, (Proc. of the Steklov Inst. Math., 9 (1958)), 1-122 · Zbl 0093.01304 |
| [24] | Post, E. L., Recursive unsolvability of a problem of Thue, J. Symbolic Logic, 13, 1-11 (1947) · Zbl 1263.03030 |
| [25] | Tarski, A., Undecidability of the theories of lattices and projective geometries, J. Symbolic Logic, 14, 77-78 (1949) |
| [26] | Whitman, P. M., Free lattices, Ann. of Math., 42, 325-330 (1941) · JFM 67.0085.01 |
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.
