Descriptive complexity theories (logic and computer sciences)

作     者：Flum, J 

作者机构：Univ Freiburg D-7800 Freiburg Germany 

出 版 物：《THEORIA-REVISTA DE TEORIA HISTORIA Y FUNDAMENTOS DE LA CIENCIA》 

年 卷 期：2003年第18卷第1期

页      面：47-58页

学科分类：0101[哲学-哲学] 07[理学] 08[工学] 0712[理学-科学技术史(分学科，可授理学、工学、农学、医学学位)] 

主　　题：computational complexity theory complexity classes descriptive characterizations monadic second-order logic fixed-point logic Turing machine 

摘      要：In this article we review some of the main results of descriptive complexity theory in order to make the reader familiarity 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.