Descriptive Complexity Theories

Citation data:

THEORIA. An International Journal for Theory, History and Foundations of Science, ISSN: 2171-679X, Vol: 18, Issue: 1, Page: 47-58

Publication Year:
Usage 157
Downloads 157
Repository URL:
Flum, Joerg
Euskal Herriko Unibertsitatea / Universidad del PaĆ­s Vasco
article description
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 a minimum.