A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Characterization and complexity of uniformly nonprimitive labeled 2-structures
Tekijät: Engelfriet J, Harju T, Proskurowski A, Rozenberg G
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 1996
Lehti:: Theoretical Computer Science
Tietokannassa oleva lehden nimi: THEORETICAL COMPUTER SCIENCE
Lehden akronyymi: THEOR COMPUT SCI
Vuosikerta: 154
Numero: 2
Aloitussivu: 247
Lopetussivu: 282
Sivujen määrä: 36
ISSN: 0304-3975
DOI: https://doi.org/10.1016/0304-3975(94)00272-X
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali