The set of the true regular protothetics formulas with partially ordered quantifiers is NEXPTIME-complete

Annals of Pure and Applied Logic 113 (1-3):53-58 (2001)
  Copy   BIBTEX

Abstract

Nondeterministic exponential time complexity bounds are established for recognizing true propositional formulas with partially ordered quantifiers on propositional variables

Categories

Keywords

Reprint years

DOI

10.1016/s0168-0072(01)00050-1

Links

PhilArchive



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

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

Partially ordered connectives and monadic monotone strict np.Lauri Hella, Merlijn Sevenster & Tero Tulenheimo - 2008 - Journal of Logic, Language and Information 17 (3):323-344.
Partially ordered quantifiers vs. partially ordered ideas.Jaakko Hintikka - 1976 - Dialectica 30 (1):89--99.
Hierarchies of Partially Ordered Connectives and Quantifiers.Michał Krynicki - 1993 - Mathematical Logic Quarterly 39 (1):287-294.
From a connected, partially ordered set of events to a partially ordered field of time intervals.P. G. Vroegindewey, V. Ja Kreinovič & O. M. Kosheleva - 1980 - Foundations of Physics 10 (5-6):469-484.
Decidability and finite axiomatizability of theories of ℵ0-categorical partially ordered sets.James H. Schmerl - 1981 - Journal of Symbolic Logic 46 (1):101 - 120.
Ways of branching quantifers.Gila Sher - 1990 - Linguistics and Philosophy 13 (4):393 - 422.
The Complexity of Bounded Quantifiers in Some Ordered Abelian Groups.Philip Scowcroft - 2007 - Notre Dame Journal of Formal Logic 48 (4):521-550.
Monoid based semantics for linear formulas.W. P. R. Mitchell & H. Simmons - 2001 - Journal of Symbolic Logic 66 (4):1597-1619.
Monoid based semantics for linear formulas.W. P. R. Mitchell & H. Simmons - 2002 - Journal of Symbolic Logic 67 (2):505-527.
Elimination of algorithmic quantifiers for ordered differential algebra.Yunfu Shen - 1999 - Archive for Mathematical Logic 38 (3):139-144.
If-logic and truth-definition.Gabriel Sandu - 1998 - Journal of Philosophical Logic 27 (2):143-164.
Partial monotonic protothetics.François Lepage - 2000 - Studia Logica 66 (1):147-163.
Partially-ordered (branching) generalized quantifiers: A general definition.Gila Sher - 1997 - Journal of Philosophical Logic 26 (1):1-43.
Decidability and ℵ0-categoricity of theories of partially ordered sets.James H. Schmerl - 1980 - Journal of Symbolic Logic 45 (3):585 - 611.

Analytics

Added to PP
2014-01-16

Downloads
20 (#761,812)

6 months
2 (#1,192,610)

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