Free lattice algorithms
type: Item
instance of: scholarly article
title: Free lattice algorithms
zbMATH Open document ID: 0627.06010
DOI: 10.1007/BF00340775
author: Ralph Freese
published in: Order
publication date: 1987-01-01T00:00:00Z
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.
reviewed by: Grigore Călugăreanu
Mathematics Subject Classification ID: 06B25
Mathematics Subject Classification ID: 06-04
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4019124
zbMATH Keywords: time complexity
zbMATH Keywords: polynomial time algorithm
zbMATH Keywords: free lattice
zbMATH Keywords: efficient algorithms
zbMATH Keywords: cover
zbMATH Keywords: implementation
zbMATH Keywords: Whitman's algorithm
MaRDI profile type: Publication
cites work: Q3956998
cites work: Splitting lattices generate all lattices
cites work: Q4055680
cites work: Projective Geometries as Projective Modular Lattices
cites work: Free Modular Lattices
cites work: Q3953813
cites work: Q3684170
cites work: Projective lattices
cites work: Covers in Free Lattices
cites work: On the Computational Complexity of Algebra on Lattices
cites work: Equational Bases and Nonmodular Lattice Varieties
cites work: What is Lisp
cites work: Free lattices
description: scientific article; zbMATH DE number 4019124