## Complexity of finitely presented algebras |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Preliminary Definitions and Results | 9 |

Completeness Results for Finitely Presented Algebras | 21 |

Isomorphism of Finitely Presented Algebras | 56 |

2 other sections not shown

### Common terms and phrases

1.1 Definition A-branches aeGr algebra presented algorithm of Theorem appears in xr arity atomic formulas axiom circuit value problem closed formulas common subterms complete for NP congruence class congruence relation Corollary deciding truth decision problems defined Definition Let denote directed graphs domain equivalent ex-j finite algebra finite set finite tree finitely presented algebras form s=t free algebra graph isomorphism hence immune induction hypothesis infinite input ISOM isomorphic via h Kozen labeled Lemma logic with equality logspace m-ary nondeterministic polynomial occurrences of variables occurs operator symbols polynomial time algorithm prenex form principal Proof Given Proof Induction Proof Let proper subterm PSPACE reduction relational symbols represented resp SATIS schema set of terms shortest proof Sn(Vn string structural induction structure subalgebra subset substring Theorem 1.2 Theorem Let trivial ueR+ universally quantified validity problem valuation verify word problem algorithm