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 algorithmsfree latticesgenerator problemuniform word problemco- NP completedeterministic logarithmic spacelog- space complete for P

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Word problems, etc. in computability and recursion theory (03D40) Free lattices, projective lattices, word problems (06B25)

Related Items (5)

Partial algebras and complexity of satisfiability and universal theory for distributive lattices, Boolean algebras and Heyting algebras ⋮ Residuated Algebraic Structures in the Vicinity of Pre-rough Algebra and Decidability ⋮ In the Shadows of the Löwenheim-Skolem Theorem: Early Combinatorial Analyses of Mathematical Proofs ⋮ A solution of the uniform word problem for ortholattices ⋮ GENERALITY AND EXISTENCE: QUANTIFICATIONAL LOGIC IN HISTORICAL PERSPECTIVE

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

This page was built for publication: The word and generator problems for lattices