Characterization and complexity of uniformly nonprimitive labeled 2-structures

• Published in: Theoretical computer science 1996-02, Vol.154 (2), p.247-282
• Main Authors: Engelfriet, J., Harju, T., Proskurowski, A., Rozenberg, G.
• Format: Article
• Language: English
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/0304-3975(94)00272-X

According to the clan decomposition theorem of Ehrenfeucht and Rozenberg (1990) each labeled 2-structure has a decomposition into three types of basic 2-structures: complete, linear and primitive. This decomposition can be expressed as a node labeled tree, the shape of the 2-structure. 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 (arc, no-arc). It is proved that forbidding primitivity in the 2-structures gives a unified approach to some well-known classes of graphs, viz., the 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 uniformly nonprimitive 2-structures and constructs their shapes. We prove also that for every MSO (monadic second-order) definable property of 2-structures, there is a LOGCF algorithm to decide whether or not a uniformly nonprimitive 2-structure has that property.