A1 Refereed original research article in a scientific journal
Characterization and complexity of uniformly nonprimitive labeled 2-structures
Authors: Engelfriet J, Harju T, Proskurowski A, Rozenberg G
Publisher: ELSEVIER SCIENCE BV
Publication year: 1996
Journal:: Theoretical Computer Science
Journal name in source: THEORETICAL COMPUTER SCIENCE
Journal acronym: THEOR COMPUT SCI
Volume: 154
Issue: 2
First page : 247
Last page: 282
Number of pages: 36
ISSN: 0304-3975
DOI: https://doi.org/10.1016/0304-3975(94)00272-X
Abstract
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.
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.
UTU Research Portal