Characterization and complexity of uniformly nonprimitive labeled 2-structures



: Engelfriet J, Harju T, Proskurowski A, Rozenberg G

Publisher: ELSEVIER SCIENCE BV

: 1996

Theoretical Computer Science

THEORETICAL COMPUTER SCIENCE

: THEOR COMPUT SCI

: 154

: 2

: 247

: 282

: 36

: 0304-3975

DOI: https://doi.org/10.1016/0304-3975(94)00272-X


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.



Last updated on 2025-13-10 at 12:31