Skip to main content


eCommons@Cornell

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: 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
76-294.pdf1.57 MBAdobe PDFView/Open
76-294.ps683.52 kBPostscriptView/Open

Refworks Export

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

 

© 2014 Cornell University Library Contact Us