The word and generator problems for lattices
From MaRDI portal
Publication:1105626
DOI10.1016/0890-5401(88)90048-XzbMath0649.06003MaRDI QIDQ1105626
Publication date: 1988
Published in: Information and Computation (Search for Journal in Brave)
polynomial-time algorithms; free lattices; generator problem; uniform word problem; co- NP complete; deterministic logarithmic space; log- space complete for P
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, 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
