TY - JOUR

T1 - Decidability of hierarchies of regular aperiodic languages

AU - Selivanov, V. L.

PY - 2002/1/1

Y1 - 2002/1/1

N2 - A new, logical approach is propounded to resolve the decidability problem for the hierarchies of Straubing and Brzozowski based on preservation theorems in model theory, a theorem of Higman, and the Rabin tree theorem. We thus manage to obtain purely logical, short proofs of some known decidability facts, which definitely may be of methodological interest. The given approach also applies in some other similar situations, for instance, to the hierarchies of formulas modulo a theory of linear orderings with finitely many unary predicates. © 2002 Plenum Publishing Corporation.

AB - A new, logical approach is propounded to resolve the decidability problem for the hierarchies of Straubing and Brzozowski based on preservation theorems in model theory, a theorem of Higman, and the Rabin tree theorem. We thus manage to obtain purely logical, short proofs of some known decidability facts, which definitely may be of methodological interest. The given approach also applies in some other similar situations, for instance, to the hierarchies of formulas modulo a theory of linear orderings with finitely many unary predicates. © 2002 Plenum Publishing Corporation.

KW - Brzozowski hierarchy

KW - Decidability

KW - Preservation theorem

KW - Regular aperiodic language

KW - Straubing hierarchy

UR - http://www.scopus.com/inward/record.url?scp=42249111727&partnerID=8YFLogxK

U2 - 10.1023/A:1020935905309

DO - 10.1023/A:1020935905309

M3 - Article

AN - SCOPUS:42249111727

VL - 41

SP - 337

EP - 348

JO - Algebra and Logic

JF - Algebra and Logic

SN - 0002-5232

IS - 5

ER -