The word and generator problems for lattices

DOI10.1016/0890-5401(88)90048-XzbMath0649.06003MaRDI QIDQ1105626

Stavros S. Cosmandakis

Publication date: 1988

Published in: Information and Computation (Search for Journal in Brave)

zbMATH Keywords

polynomial-time algorithms; free lattices; generator problem; uniform word problem; co- NP complete; deterministic logarithmic space; log- space complete for P

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

03D40: Word problems, etc. in computability and recursion theory

06B25: Free lattices, projective lattices, word problems

Related Items

In the Shadows of the Löwenheim-Skolem Theorem: Early Combinatorial Analyses of Mathematical Proofs, Partial algebras and complexity of satisfiability and universal theory for distributive lattices, Boolean algebras and Heyting algebras, A solution of the uniform word problem for ortholattices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complete problems for deterministic polynomial time
• The complexity of the word problems for commutative semigroups and polynomial ideals
• Component Subsets of the Free Lattice on n Generators
• On the algorithmic insolvability of the word problem in group theory
• Algebraic Structures with Hard Equivalence and Minimization Problems
• On the Computational Complexity of Algebra on Lattices
• Free Modular Lattices
• Word problems
• Recursive Unsolvability of a problem of Thue
• The Word Problem for Abstract Algebras
• Undecidability of Some Topological Theories
• The decision problem for some classes of sentences without quantifiers