Compression of defining pair for deterministic and strongly deterministic graphs

Abstract

For the representation of deterministic and strongly deterministic graphs by defining pairs of (multi)sets of words, we propose a class of equivalent transformations that preserve the graph represented by a correct pair. Based on these elementary transformations, we develop a compression algorithm that transforms an initial correct pair into a canonical defining pair for the same graph. The compression algorithm also provides a method for determining whether a given correct pair is a defining pair for a prescribed deterministic graph. Finally, we outline several possible applications of pair compression.