Theoria: An International Journal for Theory, History and Foundations of Science

Volume 18, Issue 1, Enero 2003

Joerg Flum
Pages 47-58

Descriptive Complexity Theories

In this article we review some of the main results of descriptive complexity theory in order to make the reader familiar with the nature of the investigations in this area. We start by presenting the characterization of automata recognizable languages by monadic second-order logic. Afterwards we explain the characterization of various logics by fIxed-point logics. We assume familiarity with logic but try to keep knowledge of complexity theory to aminimum.