Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6928
 Title: Complexity of Finitely Presented Algebras Authors: Kozen, Dexter Keywords: computer sciencetechnical report Issue Date: Dec-1976 Publisher: Cornell University Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR76-294 Abstract: An algebra $\cal 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 $\Gamma$ of defining relations $x \equiv y$ where $x$ and $y$ are well-formed terms over G and O, such that $\cal A$ is isomorphic to the free algebra on G and O modulo the congruence induced by $\Gamma$. The uniform word problem, the finiteness problem, the triviality problem (whether $\cal A$ is the one element algebra), and the subalgebra membership problem (whether a given element of $\cal A$ is contained in a finitely generated subalgebra of $\cal A$) for finitely presented algebras are shown to be $\leq^{m}_{\log}$-complete for P. The schema satisfiability problem and schema validity problem are shown to be $\leq^{m}_{\log}$-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. URI: http://hdl.handle.net/1813/6928 Appears in Collections: Computer Science Technical Reports

Files in This Item:

File Description SizeFormat