𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Sorting and doubling techniques for set partitioning and automata minimization problems

✍ Scribed by D. Ziadi

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
118 KB
Volume
231
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we present an O(n 2 ) implementation of Moore's algorithm for automata minimization. It is based on an optimal sorting procedure and on basic data structures. We also deepen the link between set partitioning problem and automata minimization problem, and assess the applicability of the doubling technique to each of these problems.

πŸ“œ SIMILAR VOLUMES

Extremal Problems for Sets Forming Boole
Extremal Problems for Sets Forming Boolean Algebras and Complete Partite Hypergraphs
✍ David S. Gunderson; VojtΔ›ch RΓΆdl; Alexander Sidorenko πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 209 KB

Three classes of finite structures are related by extremal properties: complete d-partite d-uniform hypergraphs, d-dimensional affine cubes of integers, and families of 2 d sets forming a d-dimensional Boolean algebra. We review extremal results for each of these classes and derive new ones for Bool

A combined Lagrangian, linear programmin
A combined Lagrangian, linear programming, and implication heuristic for large-scale set partitioning problems
✍ A. AtamtΓΌrk; G. L. Nemhauser; M. W. P. Savelsbergh πŸ“‚ Article πŸ“… 1996 πŸ› Springer US 🌐 English βš– 685 KB

Given a finite ground set, a set of subsets, and costs on the subsets, the set partitioning problem is to find a minimum cost partition of the ground set. Many combinatorial optimization problems can be formulated as set partitioning problems. We present an approximation algorithm that produces high