Abstract | ||
---|---|---|
Constructing an encoding of a concept lattice using short bit vectors allows for efficient computation of join operations on the lattice. Join is the central operation any unification-based parser must support. We extend the traditional bit vector encoding, which represents join failure using the zero vector, to count any vector with less than a fixed number of one bits as failure. This allows non-joinable elements to share bits, resulting in a smaller vector size. A constraint solver is used to construct the encoding, and a variety of techniques are employed to find near-optimal solutions and handle timeouts. An evaluation is provided comparing the extended representation of failure with traditional bit vector techniques. |
Year | Venue | Keywords |
---|---|---|
2010 | ACL | constraint solver,central operation,smaller vector size,short bit vector,traditional bit vector encoding,generalized-zero-preserving method,traditional bit vector technique,concept lattice,compact encoding,share bit,efficient computation,zero vector |
Field | DocType | Volume |
Null vector,Computer science,Unification,Bit field,Algorithm,Constraint satisfaction problem,Parsing,Bit array,Encoding (memory),Computation | Conference | P10-1 |
Citations | PageRank | References |
4 | 0.50 | 11 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Matthew Skala | 1 | 101 | 12.52 |
Victoria Krakovna | 2 | 4 | 0.50 |
János Kramár | 3 | 63 | 4.26 |
Gerald Penn | 4 | 1039 | 77.13 |