Descriptive complexity theories
Theoria 18 (1):47-58 (2003)
| 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 aminimum | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,711 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesJacek Hawranek & Jan Zygmunt (1981). On the Degree of Complexity of Sentential Logics. A Couple of Examples. Studia Logica 40 (2):141 - 153.
Mark Schroeder (forthcoming). Semantics, Moral. In Hugh LaFollette (ed.), International Encyclopedia of Ethics. Wiley.
Ralph H. Abraham (2011). The Genesis of Complexity. World Futures 67 (4-5):380 - 394.
Leszek Aleksander Kołodziejczyk (2004). Truth Definitions in Finite Models. Journal of Symbolic Logic 69 (1):183-200.
Peter Stewart (2001). Complexity Theories, Social Theory, and the Question of Social Complexity. Philosophy of the Social Sciences 31 (3):323-360.
Michael Lamport Commons & Alexander Pekker (2008). Presenting the Formal Theory of Hierarchical Complexity. World Futures 64 (5 - 7):375 – 382.
Lauri Hella, Phokion G. Kolaitis & Kerkko Luosto (1996). Almost Everywhere Equivalence of Logics in Finite Model Theory. Bulletin of Symbolic Logic 2 (4):422-443.
Martin Grohe (1998). Finite Variable Logics in Descriptive Complexity Theory. Bulletin of Symbolic Logic 4 (4):345-398.
Felipe Cucker & Klaus Meer (1999). Logics Which Capture Complexity Classes Over the Reals. Journal of Symbolic Logic 64 (1):363-390.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2009-01-28Total downloads0Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
