eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >
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 science technical report 
Issue Date:  Dec1976 
Publisher:  Cornell University 
Citation:  http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR76294 
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 wellformed 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 coNP, respectively, Finally, the problem of isomorphism of finitely presented algebras is shown to be polynomial time manyone equivalent to the problem of graph isomorphism. 
URI:  http://hdl.handle.net/1813/6928 
Appears in Collections:  Computer Science Technical Reports

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.
