Navegar

Colección

Datos Estadísticas

Artículo

Figueira, S.; Gorín, D.; Grimson, R.; Beklemishev L.D.; Queiroz R. "On the expressive power of IF-logic with classical negation" (2011) 18th International Workshop on Logic, Language, Information and Computation, WoLLIC 2011. 6642 LNAI:135-145
La versión final de este artículo es de uso interno. El editor solo permite incluir en el repositorio el artículo en su versión post-print. Por favor, si usted la posee enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

It is well-known that Independence Friendly (IF) logic is equivalent to existential second-order logic ((formula presnted)) and, therefore, is not closed under classical negation. The boolean closure of IF sentences, called Extended IF-logic, on the other hand, corresponds to a proper fragment of (formula presnted). In this paper we consider IF-logic extended with Hodges’ flattening operator, which allows classical negation to occur also under the scope of IF quantifiers. We show that, nevertheless, the expressive power of this logic does not go beyond (formula presnted). As part of the proof, we give a prenex normal form result and introduce a non-trivial syntactic fragment of full second-order logic that we show to be contained in (formula presnted). © 2011, Springer-Verlag Berlin Heidelberg.

Registro:

Documento: Artículo
Título:On the expressive power of IF-logic with classical negation
Autor:Figueira, S.; Gorín, D.; Grimson, R.; Beklemishev L.D.; Queiroz R.
Filiación:Dto. Computación, FCEN, Universidad de Buenos Aires, Argentina
Dto. Matemática, FCEN, Universidad de Buenos Aires, Argentina
CONICET, Argentina
Palabras clave:Computation theory; Existential second-order logic; Expressive power; Non-trivial; Prenex normal forms; Second-order logic; Computer circuits
Año:2011
Volumen:6642 LNAI
Página de inicio:135
Página de fin:145
DOI: http://dx.doi.org/10.1007/978-3-642-20920-8_16
Título revista:18th International Workshop on Logic, Language, Information and Computation, WoLLIC 2011
Título revista abreviado:Lect. Notes Comput. Sci.
ISSN:03029743
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v6642LNAI_n_p135_Figueira

Referencias:

  • Caicedo, X., Krynicki, M., Quantifiers for reasoning with imperfect information and Σ1-logic.1 (1999) Contemporary Mathematics, 235, pp. 17-31
  • Enderton, H., Finite partially ordered quantifiers (1970) Zeitschrift für Mathematische Logik Und Grundlagen Der Mathematik, 16, pp. 393-397
  • Figueira, S., Gorín, D., Grimson, R., On the formal semantics of IF-like logics (2009) Journal of Computer and System Sciences, 76 (5), pp. 333-346
  • Hintikka, J., (1996) The Principles of Mathematics Revisited, , Cambridge University Press, Cambridge
  • Hintikka, J., Sandu, G., Game-theoretical semantics (1997) Handbook of Logic and Language, , van Benthem, J., ter Meulen, A. (eds.), The MIT press, Cambridge
  • Hodges, W., Compositional semantics for a language of imperfect information (1997) Logic Journal of the IGPL, 5 (4)
  • Janssen, T.M.V., Independent choices and the interpretation of IF logic (2002) Journal of Logic, Language and Information, 11 (3), pp. 367-387
  • Janssen, T.M.V., Dechesne, F., Signalling in IF games: A tricky business (2006) The Age of Alternative Logics, pp. 221-241. , Springer, Heidelberg
  • Ko̷lodziejczyk, L.A., (2002) He Expressive Power of Henkin Quantifiers with Dualization. Master’s Thesis, Institute of Philosophy, , arsaw University, Poland
  • Mostowski, M., Arithmetic with the Henkin quantifier and its generalizations. In: Gaillard, F., Richard, D. (eds.) Séminaire du Laboratoire Logique (1991) Algorithmique Et Informatique Clermontoise, 2, pp. 1-25
  • Väänänen, J.A., On the semantics of informational independence (2002) Logic Journal of the IGPL, 10 (3), pp. 339-352A4 -

Citas:

---------- APA ----------
Figueira, S., Gorín, D., Grimson, R., Beklemishev L.D. & Queiroz R. (2011) . On the expressive power of IF-logic with classical negation. 18th International Workshop on Logic, Language, Information and Computation, WoLLIC 2011, 6642 LNAI, 135-145.
http://dx.doi.org/10.1007/978-3-642-20920-8_16
---------- CHICAGO ----------
Figueira, S., Gorín, D., Grimson, R., Beklemishev L.D., Queiroz R. "On the expressive power of IF-logic with classical negation" . 18th International Workshop on Logic, Language, Information and Computation, WoLLIC 2011 6642 LNAI (2011) : 135-145.
http://dx.doi.org/10.1007/978-3-642-20920-8_16
---------- MLA ----------
Figueira, S., Gorín, D., Grimson, R., Beklemishev L.D., Queiroz R. "On the expressive power of IF-logic with classical negation" . 18th International Workshop on Logic, Language, Information and Computation, WoLLIC 2011, vol. 6642 LNAI, 2011, pp. 135-145.
http://dx.doi.org/10.1007/978-3-642-20920-8_16
---------- VANCOUVER ----------
Figueira, S., Gorín, D., Grimson, R., Beklemishev L.D., Queiroz R. On the expressive power of IF-logic with classical negation. Lect. Notes Comput. Sci. 2011;6642 LNAI:135-145.
http://dx.doi.org/10.1007/978-3-642-20920-8_16