Sébastien Ferré

LSet: sets as ordered polymorphic lists ( lSet.ml )
This module implements polymorphic sets as polymorphic lists whose elements are ordered according to the reverse of the OCaml function Pervasives.compare. Most set operations are in linear time in the size of sets, and iterations on lists are available.

Cis: compact integer sets ( cis.mli | cis.ml )
This module implements compact integer sets, represented as a (custom) list of integer intervals. Usual set operations are provided. The advantage compared to ordered lists is that the actual size may be smaller than the cardinal of a set when many elements are contiguous. Most set operations are linear w.r.t. the size of the structure, not the cardinal of the set.

Suffix_tree: generalized suffix trees ( suffix_tree.ml ) [ depends on LSet, Cis ]
This module implements generalized suffix trees (GST). A GST is defined by a set of strings, in which strings can be added or removed, and is represented as the compact lexical tree of all suffixes of these strings. Every node of the tree corresponds to a substring that is present in one or more strings. Some of these substrings are said maximal when every other substring or string that contains it is present in fewer strings. The construction of a GST is in linear time and linear space w.r.t. the cumulated size of strings, with a rather high constant factor for space though (about 10-20). It supports the incremental addition or removal of a string. Many low- and high-level access functions are provided. A readable simplified form of GSTs is provided for toplevel use.

Algorithms

Iceberg: a program for computing all frequent formal concepts from a formal context (iceberg-1.0.tar.gz)
This program uses an adaptation of Bordat's algorithm for computing the concept lattice. This adaptation can use a minimum size for extents (a.k.a. minimum support), and is programmed as a fold function through all frequent concepts. Iceberg can output the intent, extent, and/or support of each concept, gives some simple statistics about the context, and also outputs at the end the number of computed concepts, and the execution time for the folding (not counting the reading and preprocessing stages).
It is accompanied by a utility program that converts a CSV file representing a multi-valued context to a context file acceptable by Iceberg.

Libraries

Logfun: a library of logic functors
A logic functor is a function that can be applied to zero, one or several logics so as to produce a new logic as a combination of argument logics. Each argument logic can itself be built by combination of logic functors. The signature of a logic is made of a parser and a printer of formulas, logical operations such as a theorem prover for entailment between formulas, and more specific operations required by Logical Information Systems (LIS). Logic functors can be concrete domains like integers, strings, or algebraic combinators like product or sum of logics.

Software