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

Preview

PDF 409-728-1-PB.pdf - Published Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (715kB)

Abstract

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
Creators:	Creators Email ORCID Flum, Joerg Joerg.Flum@mathematik.uni-freiburg.de
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:	http://www.ehu.es/ojs/index.php/THEORIA/article/vi...
DOI or Unique Handle:	10.1387/theoria.409
Date:	2003
Page Range:	pp. 47-58
Volume:	18
Number:	1
ISSN:	2171-679X
URI:	https://philsci-archive.pitt.edu/id/eprint/10538

Monthly Views for the past 3 years

Monthly Downloads for the past 3 years

Plum Analytics

Altmetric.com

Actions (login required)

View Item