Electronic Resource
Springer
Order
3 (1987), S. 331-344
ISSN:
1572-9273
Keywords:
06B25
;
68C25
;
Free lattice
;
cover
;
algorithm
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract In the late 1930s Phillip Whitman gave an algorithm for deciding for lattice terms v and u if v≤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 this term is unique up to commutivity and associativity. He gave an algorithm for finding this term. Almost all the work on free lattices uses these algorithms. Building on the work of Ralph McKenzie, J. B. Nation and the author have developed very efficient algorithms for deciding if a lattice term v has a lower cover (i.e., if there is a w with w covered by v, which is denoted by w〈v) and for finding them if it does. This paper studies the efficiency of both Whitman's algorithm and the algorithms of Freese and Nation. It is shown that although it is often quite fast, the straightforward implementation of Whitman's algorithm for testing v≤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 then shown to be polynomial.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF00340775
Permalink
| Library |
Location |
Call Number |
Volume/Issue/Year |
Availability |
