On a decidable generalized quantifier logic corresponding to a decidable fragment of first-order logic
Graduate studies at Western
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||categorize this paper)|
|Through your library||Configure|
Similar books and articles
Franç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):19-58.
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):263-279.
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 (2011). An Event-Based Fragment of First-Order Logic Over Intervals. Journal of Logic, Language and Information 20 (1):49-68.
Added to index2009-01-28
Total downloads6 ( #154,923 of 739,392 )
Recent downloads (6 months)0
How can I increase my downloads?