Free lattice algorithms

DOI10.1007/BF00340775MaRDI QIDQ581431zbMATH OpenFDO

Authors Ralph Freese

Publication date 1987

Published in Order (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF00340775

zbMATH Keywords

coverefficient algorithmsfree latticeimplementationpolynomial time algorithmtime complexityWhitman's algorithm

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to ordered structures (06-04) Free lattices, projective lattices, word problems (06B25) Analysis of algorithms and problem complexity (68Q25)

Review text

In the late 1930s Philip Whitman gave an algorithm for deciding for lattice terms \(v\) and \(u\) if \(v\leq u\) in the free lattice on the variables in \(v\) and \(u\). He also showed that each element of the free lattice has a shortest term representing it and gave an algorithm for finding this term. Using Ralph McKenzie's work, J. B. Nation and the author have developed efficient algorithms for deciding if a lattice term v has a lower cover and for finding them if it does. This paper studies the efficiency of all these algorithms. It is shown that although it is often quite fast, the straightforward implementation of Whitman's algorithm for testing \(v\leq u\) is exponential in time in the worst case. A modification of Whitman's algorithm is given which is polynomial and has constant minimum time. The algorithms of Freese and Nation are also shown to be polynomial.

Recommendations

• scientific article; zbMATH DE number 758787
• A fast algorithm for building lattices
• Finitely Presented Lattices: Canonical Forms and the Covering Relation
• scientific article; zbMATH DE number 3849292
• On the Computational Complexity of Algebra on Lattices

Cites work

• Covers in Free Lattices
• Equational Bases and Nonmodular Lattice Varieties
• Free lattices
• Free Modular Lattices
• scientific article; zbMATH DE number 3906552 (Why is no real title available?)
• scientific article; zbMATH DE number 3773659 (Why is no real title available?)
• scientific article; zbMATH DE number 3777562 (Why is no real title available?)
• scientific article; zbMATH DE number 3472104 (Why is no real title available?)
• On the Computational Complexity of Algebra on Lattices
• Projective Geometries as Projective Modular Lattices
• Projective lattices
• Splitting lattices generate all lattices
• What is Lisp

Cited in

(8)

• Singular covers in free lattices
• Jónsson's contributions to lattice theory
• Symmetric embeddings of free lattices into each other
• Computers and universal algebra: Some directions
• A visual approach to test lattices
• Finitely Presented Lattices: Canonical Forms and the Covering Relation
• Polynomial-time equational theory for lattices with unary operators
• On the uniform word problem for lattices

This page was built for publication: Free lattice algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q581431)