More on -Separating Systems
Gérard Cohen, Sylvia Encheva, Hans Georg Schaathun · Surrey Research Insight Open Access (The University of Surrey) · 2002
Abstract— Thetheory ofseparatingsystemshas beenappliedin differentareas of science and technology such as automata synthesis, technical diag-nosis, and authenticating ownership claims. Constructions of (2 2) -sepa-rating systems derivedfromerror-correctingcodes aregiven,together withbounds on their parameters based on distance considerations.Index Terms— Copyright protection, error-correcting codes, separatingsystems, watermarking. I. I NTRODUCTION The case of (2 ; 2) -separation was introduced by Sagalovich in thecontext of automata: two such systems transiting simultaneously fromstate a to a 0 and from b to b 0 , respectively, should be forbidden to passthrough a common intermediate state. He has written a long series ofpapers since the 1960s, a fairly recent survey can be found in [1]. Statesare simply binary n -tuples and only shortest paths are allowed duringtransitions; in other words, the only “moves” permitted while transitingfrom a to a 0 are complementing the d ( a; a ) bits where a and a