REDUCTIONS FOR PRIMITIVE 2-STRUCTURES

Article type: Research Article

Authors: Harju, T. | Rozenberg, G.

Affiliations: Department of Mathematics, University of Turku, SF-20500 Turku, Finland | Department of Computer Science, Leiden University P.O. Box 9512, 2300 RA Leiden, The Netherlands and Department of Computer Science, University of Colorado at Boulder, Boulder, CO 80309, U.S.A.

Abstract: A subset X of a 2-structure (a reversible edge-colored directed graph) g is a clan, if X cannot be distinguished by colors from outside of X. We show that if g is primitive, i.e. it has no nontrivial clans, then there exists an edge e or an end vertex x such that when e or x is removed from g, the resulting 2-structure g′ remains primitive. We also present a composition result for the unstable 2-structures, which are those primitive 2-structures where a removal of any edge results in a nonprimitive 2-structure.

DOI: 10.3233/FI-1994-201235

Journal: Fundamenta Informaticae, vol. 20, no. 1,2,3, pp. 133-144, 1994