Repository URL:
http://philsci-archive.pitt.edu/id/eprint/10538
DOI:
10.1387/theoria.409
Author(s):
Flum, Joerg
Publisher(s):
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.

This article has 0 Wikipedia mention.