Approximate formulae for a logic that capture classes of computational complexity

&
Logic Journal of the IGPL 17 (1):131-154 (2008)
  Copy   BIBTEX

Abstract

This paper presents a syntax of approximate formulae suited for the logic with counting quantifiers

Categories

Keywords

Reprint years

2009

DOI

10.1093/jigpal/jzn031

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,783

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

On the Capture of Complexity Classes Using Logic.I. A. Stewart - 1991 - University of Newcastle Upon Tyne, Computing Laboratory.
Logics which capture complexity classes over the reals.Felipe Cucker & Klaus Meer - 1999 - Journal of Symbolic Logic 64 (1):363-390.
Approximate Counting in Bounded Arithmetic.Emil Jeřábek - 2007 - Journal of Symbolic Logic 72 (3):959 - 993.
Context-sensitive transitive closure operators.Iain A. Stewart - 1994 - Annals of Pure and Applied Logic 66 (3):277-301.
An approximate approach to belief revision.Shangmin Luan, Guozhong Dai & Lorenzo Magnani - 2012 - Logic Journal of the IGPL 20 (2):486-496.
Review: O. B. Lupanov, G. R. Kiss, On the Realization of Functions of Logical Algebra by Formulae of Finite Classes (Formulae of Limited Depth) in the Basis &, $vee$, $^-$. [REVIEW]Louis Hodes - 1971 - Journal of Symbolic Logic 36 (3):547-547.
Spectra of formulae with Henkin quantifiers.Joanna Golinska-Pilarek & Konrad Zdanowski - 2003 - In A. Rojszczak, J. Cachro & G. Kurczewski (eds.), Philosophical Dimensions of Logic and Science. Kluwer Academic Publishers. pp. 29-45.
Capturing Relativized Complexity Classes with Lindström Quantifiers.Janos Makowsky - 1995 - Vienna Circle Institute Yearbook 3:133-140.
Public announcements, public assignments and the complexity of their logic.Hans van Ditmarsch, Andreas Herzig & Tiago De Lima - 2012 - Journal of Applied Non-Classical Logics 22 (3):249-273.
Equality and monodic first-order temporal logic.Anatoli Degtyarev, Michael Fisher & Alexei Lisitsa - 2002 - Studia Logica 72 (2):147-156.
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.
Computation models for parameterized complexity.Marco Cesati & Miriam Dilanni - 1997 - Mathematical Logic Quarterly 43 (2):179-202.
Capturing Relativized Complexity Classes without Order.Anuj Dawar, Georg Gottlob & Lauri Hella - 1998 - Mathematical Logic Quarterly 44 (1):109-122.
Elementary classes in basic modal logic.Holger Sturm - 2000 - Studia Logica 64 (2):193-213.
A Finite Fragment Of S3.Tomasz Kowalski & John Slaney - 2008 - Reports on Mathematical Logic.

Analytics

Added to PP
2015-02-04

Downloads
2 (#1,802,998)

6 months
1 (#1,467,486)

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