CHARACTERIZATION AND COMPLEXITY OF UNIFORMLY NONPRIMITIVE LABELED 2-STRUCTURES

According to the dan decomposition theorem of Ehrenfeucht and Rozenber g (1990) each labeled 2-structure has a decomposition into three types of basic 2-structures: complete, linear and primitive. This decomposi tion can be expressed as a node labeled tree, the shape of the 2-struc ture. Our main interest is in the uniformly nonprimitive 2-structures, which do not have primitive substructures. Every (directed) graph can be considered as a restricted 2-structure with only two labels (are, no-are). It is proved that forbidding primitivity in the 2-structures gives a unified approach to some well-known classes of graphs, viz., t he cographs and the transitive vertex series-parallel graphs. We also study the parallel complexity of the decomposition of 2-structures. It is shown that there is a LOGCF algorithm, which recognizes the unifor mly nonprimitive 2-structures and constructs their shapes. We prove al so that for every MSO (monadic second-order) definable property of 2-s tructures, there is a LOGCF algorithm to decide whether or not a unifo rmly nonprimitive 2-structure has that property.