On a decidable generalized quantifier logic corresponding to a decidable fragment of first-order logic
Journal of Logic, Language and Information 4 (3):177-189 (1995)
| Abstract | Van Lambalgen (1990) proposed a translation from a language containing a generalized quantifierQ into a first-order language enriched with a family of predicatesR i, for every arityi (or an infinitary predicateR) which takesQxg(x, y1,..., yn) to x(R(x, y1,..., y1) (x,y1,...,yn)) (y 1,...,yn are precisely the free variables ofQx). The logic ofQ (without ordinary quantifiers) corresponds therefore to the fragment of first-order logic which contains only specially restricted quantification. We prove that it is decidable using the method of analytic tableaux. Related results were obtained by Andréka and Németi (1994) using the methods of algebraic logic | |||||||||
| 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,664 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesFrançoise Maurin (1997). The Theory of Integer Multiplication with Order Restricted to Primes is Decidable. Journal of Symbolic Logic 62 (1):123-130.
Wiebe Van Der Hoek & Maarten De Rijke (1993). Generalized Quantifiers and Modal Logic. Journal of Logic, Language and Information 2 (1).
Juha Kontinen (2006). The Hierarchy Theorem for Second Order Generalized Quantifiers. Journal of Symbolic Logic 71 (1):188 - 202.
Yves Lafont (1996). The Undecidability of Second Order Linear Logic Without Exponentials. Journal of Symbolic Logic 61 (2):541-548.
Alexander Paseau (2010). Pure Second-Order Logic with Second-Order Identity. Notre Dame Journal of Formal Logic 51 (3):351-360.
Johan van Benthem (2005). Guards, Bounds, and Generalized Semantics. Journal of Logic, Language and Information 14 (3).
Juha Kontinen & Jakub Szymanik (2011). Characterizing Definability of Second-Order Generalized Quantifiers. In L. Beklemishev & R. de Queiroz (eds.), Proceedings of the 18th Workshop on Logic, Language, Information and Computation, Lecture Notes in Artificial Intelligence 6642. Springer.
Walter Hussak (2008). Decidable Cases of First-Order Temporal Logic with Functions. Studia Logica 88 (2):247 - 261.
Erich Grädel (1999). On the Restraining Power of Guards. Journal of Symbolic Logic 64 (4):1719-1742.
Savas Konur (forthcoming). An Event-Based Fragment of First-Order Logic Over Intervals. Journal of Logic, Language and Information.
Analytics
Monthly downloads |
Added to index2009-01-28Total downloads6 ( #145,498 of 549,011 )Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
