Capturing Relativized Complexity Classes with Lindström Quantifiers

Vienna Circle Institute Yearbook 3:133-140 (1995)
  Copy   BIBTEX

Abstract

In the last 20 years several logics were exhibited which capture complexity classes such as L , NL , P , NP , PH , [4, 12, 13, 23, 20] on ordered structures. In mathematical logic the theory of abstract model theory and Lindström quantifiers is well established [2]. In this talk we report our work concerning unification of Descriptive Complexity Theory andModel Theory. A detailed account has been published in [15, 16, 17]. Similar results with complementary aims have been proven recently by G. Gottlob, [6]

Categories

Keywords

Reprint years

DOI

10.1007/978-94-017-3327-4_10

Other Versions

No versions found

Links

PhilArchive

    This entry is not archived by us. If you are the author and have permission from the publisher, we recommend that you archive it. Many publishers automatically grant permission to authors to archive pre-prints. By uploading a copy of your work, you will enable us to better index it, making it easier to find.

    Upload a copy of this work     Papers currently archived: 105,859

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Capturing Relativized Complexity Classes without Order.Anuj Dawar, Georg Gottlob & Lauri Hella - 1998 - Mathematical Logic Quarterly 44 (1):109-122.
Almost everywhere equivalence of logics in finite model theory.Lauri Hella, Phokion G. Kolaitis & Kerkko Luosto - 1996 - Bulletin of Symbolic Logic 2 (4):422-443.
Finite Model Theory.Heinz-Dieter Ebbinghaus & Jörg Flum - 2005 - Springer.
Logics which capture complexity classes over the reals.Felipe Cucker & Klaus Meer - 1999 - Journal of Symbolic Logic 64 (1):363-390.
Complexity of the Universal Theory of Residuated Ordered Groupoids.Dmitry Shkatov & C. J. Van Alten - 2023 - Journal of Logic, Language and Information 32 (3):489-510.
Saturation and stability in the theory of computation over the reals.Olivier Chapuis & Pascal Koiran - 1999 - Annals of Pure and Applied Logic 99 (1-3):1-49.
Relativized logspace and generalized quantifiers over finite ordered structures.Georg Gottlob - 1997 - Journal of Symbolic Logic 62 (2):545-574.
Monotonicity and the Expressibility of NP Operators.Iain A. Stewart - 1994 - Mathematical Logic Quarterly 40 (1):132-140.
The hierarchy theorem for generalized quantifiers.Lauri Hella, Kerkko Luosto & Jouko Väänänen - 1996 - Journal of Symbolic Logic 61 (3):802-817.
Succinctness as a source of complexity in logical formalisms.Georg Gottlob, Nicola Leone & Helmut Veith - 1999 - Annals of Pure and Applied Logic 97 (1-3):231-260.

Analytics

Added to PP
2015-01-22

Downloads
15 (#1,332,171)

6 months
1 (#1,599,047)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references