Complexity of finitely presented algebras

ABSTRACT

An algebra A is finitely presented if there is a finite set G of generator symbols, a finite set O of operator symbols, and a finite set &Ggr; of defining relations x&Xgr;y where x and y are well-formed terms over G and O, such that A is isomorphic to the free algebra on G and O modulo the congruence induced by &Ggr;. The uniform word problem, the finiteness problem, the triviality problem (whether A is the one element algebra), and the subalgebra membership problem (whether a given element of A is contained in a finitely generated subalgebra of A) for finitely presented algebras are shown to be ≤mlog-complete for P. The schema satisfiability problem and schema validity problem are shown to be ≤mlog-complete for NP and co-NP, respectively. Finally, the problem of isomorphism of finitely presented algebras is shown to be polynomial time many-one equivalent to the problem of graph isomorphism.

REFERENCES

• 1: Lipton, R.J. and Y. Zalcstein, Word Problems Solvable in Logspace, Technical Report #48, Department of Computer Science, SUNY at Stony Brook, 1975.
• 2: E. Cardoza , R. Lipton , A. R. Meyer, Exponential space complete problems for Petri nets and commutative semigroups (Preliminary Report), Proceedings of the eighth annual ACM symposium on Theory of computing, p.50-54, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803630]
• 3: Richard E. Ladner, The circuit value problem is log space complete for P, ACM SIGACT News, v.7 n.1, p.18-20, January 1975 [doi>10.1145/990518.990519]
• 4: Neil D. Jones , William T. Laaser, Complete problems for deterministic polynomial time, Proceedings of the sixth annual ACM symposium on Theory of computing, p.40-46, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803883]
• 5: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 6: Kozen, D., "On Parallelism in Turing Machines," Proc. 17th IEEE Symposium on Foundations of Computer Science, October 1976, 89-97.
• 7: L. J. Stockmeyer , A. R. Meyer, Word problems requiring exponential time(Preliminary Report), Proceedings of the fifth annual ACM symposium on Theory of computing, p.1-9, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804029]
• 8: Richard E. Ladner, Polynominal time reducibility, Proceedings of the fifth annual ACM symposium on Theory of computing, p.122-129, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804042]
• 9: John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
• 10: Thatcher, J.W., "Tree Automata: An Informal Survey," Currents in the Theory of Computing, ed. Aho, Prentice-Hall, Englewood Cliffs, N.J, 1973.
• 11: Engelfriet, J., "Tree Automata and Tree Grammars," Department of Computer Science Report DAIMI FN-10, University of Aarhus, Denmark, April 1975.
• 12: Thatcher, J.W., and J.B. Wright, "Generalized Finite Automata Theory with an Application to a Decision Problem of Second Order Logic," Math. Syst. Th. 2, 1968.
• 13: Doner, J., "Decidability of the Weak Second Order Theory of Two Sucsessors," Notices Am. Math. Soc. 12, 1965.
• 14: Rabin, M.O., "Decidability of Second Order Theories and Automata on Infinite Trees," Trans, Am. Math Soc. 141.
• 15: Booth, K.S., "Problems Polynomially Equivalent to Graph Isomorphism," Carnegie-Mellon Symposium on New Directions and Recent Results in Algorithms and Complexity, April 1976.
• 16: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 17: Dexter Kozen, Complexity of Finitely Presented Algebras, Cornell University, Ithaca, NY, 1976
• 18: Dexter Kozen, Finitely Presented Algebras and the Polynomial Time Hiercharchy, Cornell University, Ithaca, NY, 1977

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.1 Expressions and Their Representation
          Subjects: Representations (general and polynomial)

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

General Terms:
Algorithms, Performance, Theory