A synthesis on partition refinement: A useful routine for strings, graphs, boolean matrices and automata | Zendy

Michel Habib | Zendy; Christophe Paul | Zendy; Laurent Viennoti | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

A synthesis on partition refinement: A useful routine for strings, graphs, boolean matrices and automata

Author(s) -

Michel Habib,

Christophe Paul,

Laurent Viennoti

Publication year - 1998

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

ISBN - 3-540-64230-7

DOI - 10.1007/bfb0028546

Subject(s) - computer science , correctness , partition (number theory) , theoretical computer science , automaton , equivalence (formal languages) , mathematical proof , algorithm , discrete mathematics , mathematics , combinatorics , geometry

The original publication is available at www.springerlink.comInternational audiencePartition refinement techniques are used in many algorithms. This tool allows efficient computation of equivalence relations and is somehow dual to union-find algorithms. The goal of this paper is to propose a single routine to quickly implement all these already known algorithms and to solve a large class of potentially new problems. Our framework yields to a unique scheme for correctness proofs and complexity analysis. Various examples are presented to show the different ways of using this routine

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research