PhilSci Archive

Descriptive Complexity Theories

Flum, Joerg (2003) Descriptive Complexity Theories. THEORIA. An International Journal for Theory, History and Foundations of Science, 18 (1). pp. 47-58. ISSN 2171-679X

409-728-1-PB.pdf - Published Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (715kB)


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.

Export/Citation: EndNote | BibTeX | Dublin Core | ASCII/Text Citation (Chicago) | HTML Citation | OpenURL
Social Networking:
Share |

Item Type: Published Article or Volume
Additional Information: ISSN: 0495-4548 (print)
Keywords: Computational complexity theory, complexity classes, descriptive characterizations, monadic second-order logic, fixed-point logic, Turing machine
Depositing User: Users 15304 not found.
Date Deposited: 04 Mar 2014 19:49
Last Modified: 11 Mar 2014 20:58
Item ID: 10538
Journal or Publication Title: THEORIA. An International Journal for Theory, History and Foundations of Science
Publisher: Euskal Herriko Unibertsitatea / Universidad del País Vasco
Official URL:
DOI or Unique Handle:
Date: 2003
Page Range: pp. 47-58
Volume: 18
Number: 1
ISSN: 2171-679X

Monthly Views for the past 3 years

Monthly Downloads for the past 3 years

Plum Analytics

Actions (login required)

View Item View Item