A category theory approach to conceptual data modeling
A limiting distribution for quicksort
A model of regular sparsity map representation.
A New Approach to the Dynamic Maintenance of Maximal Points in a Plane.
A partially persistent data structure for the set-union problem
A perfect hashing incremental scheme for unranked trees using pseudo-minimal automata
We describe a technique that maps unranked trees to arbitrary hash codes using a bottom-up deterministic tree automaton (DTA). In contrast to other hashing techniques based on automata, our procedure builds a pseudo-minimal DTA for this purpose. A pseudo-minimal automaton may be larger than the minimal one accepting the same language but, in turn, it contains proper elements (states or transitions which are unique) for every input accepted by the automaton. Therefore, pseudo-minimal DTA...
A semantic construction of two-ary integers
To binary trees, two-ary integers are what usual integers are to natural numbers, seen as unary trees. We can represent two-ary integers as binary trees too, yet with leaves labelled by binary words and with a structural restriction. In a sense, they are simpler than the binary trees, they relativize. Hence, contrary to the extensions known from Arithmetic and Algebra, this integer extension does not make the starting objects more complex. We use a semantic construction to get this extension. This...
Algebraic definition of a functional programming language and its semantic models
An algorithm to compute the möbius function of the rotation lattice of binary trees
An application of -ary trees to the design of data structures for geometric searching problems
Arbitrary weight changes in dynamic trees
Associative models for storing and retrieving concept lattices.
Average case analysis of fully dynamic reachability for directed graphs
Canonical decomposition of outerplanar maps and application to enumeration, coding and generation.
Categorical abstract data type (CADT)
Challenging complexity of maximum common subgraph detection algorithms: A performance analysis of three algorithms on a wide database of graphs.
Characterizing the complexity of boolean functions represented by well-structured graph-driven parity-FBDDs
We investigate well-structured graph-driven parity-FBDDs, which strictly generalize the two well-known models parity OBDDs and well-structured graph-driven FBDDs. The first main result is a characterization of the complexity of Boolean functions represented by well-structured graph-driven parity-FBDDs in terms of invariants of the function represented and the graph-ordering used. As a consequence, we derive a lower bound criterion and prove an exponential lower bound for certain linear code functions....
Characterizing the Complexity of Boolean Functions represented by Well-Structured Graph-Driven Parity-FBDDs
We investigate well-structured graph-driven parity-FBDDs, which strictly generalize the two well-known models parity OBDDs and well-structured graph-driven FBDDs. The first main result is a characterization of the complexity of Boolean functions represented by well-structured graph-driven parity-FBDDs in terms of invariants of the function represented and the graph-ordering used. As a consequence, we derive a lower bound criterion and prove an exponential lower bound for certain linear code functions. The...
Constructing Binary Huffman Tree
Huffman coding is one of a most famous entropy encoding methods for lossless data compression [16]. JPEG and ZIP formats employ variants of Huffman encoding as lossless compression algorithms. Huffman coding is a bijective map from source letters into leaves of the Huffman tree constructed by the algorithm. In this article we formalize an algorithm constructing a binary code tree, Huffman tree.
Construction, évaluation et amélioration systématiques de structures de données