Copyright and Licensing
Articles accepted for publication will be licensed under the Creative Commons BY-NC-SA. Authors must sign a non-exclusive distribution agreement after article acceptance.
Capturing relational NEXPTIME with a fragment of existential third order logic
Keywords:
relational complexity, third order logic, expressibility of logics, relational machines, fixed point quantifiersAbstract
We prove that the existential fragment Σ^(2,ω) 1 of the third order logic TO^ω
captures the relational complexity class non deterministic exponential time. As a Corollary we have that relational machines that work in NEXTIME r can simulate third order relational machines that work in NEXPTIME 3,r.
Downloads
Download data is not yet available.
References
[1] J. Arroyuelo, J. M. Turull-Torres, “The Existential Fragment of Third Order Logic and Third Order Relational Machines”, in “Proceedings of the XIX Argentine Conference on Computer Science CACIC 2014”, ISBN 978-987-3806-05-6, Buenos Aires, October 20-24, p. 324-333, 2014.
[2] Abiteboul, S., Vianu, V., “Generic Computation and its Complexity”, STOC 1991.
[3] Abiteboul, S., Vardi, M., Vianu, V., “Computing with Infinitary Logic”, Theoretical Computer Science 149, 1, pp. 101-128, 1995.
[4] Abiteboul, S., Vardi, M. Y., Vianu, V., “Fixpoint logics, relational machines, and computational complexity”, JACM 44 (1997) 30-56.
[5] Dawar, A., “A restricted second order logic for finite structures”. Information and Computation 143 (1998) 154-174.
[6] Fagin, R., “Generalized First-Order Spectra and Polynomial-Time Recognizable Sets”, in “Complexity of Computations”, edited by R. Karp, SIAM-AMS Proc., American Mathematical Society, Providence, RI, pp. 27–41, 1974.
[7] F. A. Ferrarotti, A. L. Paoletti, J. M. Turull-Torres, “Redundant Relations in Relational Databases: A Model Theoretic Perspective”, Journal of Universal Computer Science, Vol. 16, No. 20, pp. 2934-2955, 2010. http://www.jucs.org/jucs 16 20/redundant relations in relational
[8] Ferrarotti, F. A., Turull-Torres, J. M., “The Relational Polynomial-Time Hierarchy and Second-Order Logic”, invited for “Semantics in Databases”, edited by K-D. Schewe and B. Thalheim, Springer LNCS 4925, 29 pages, 2008.
[9] Grosso, A. L., Turul-Torres J. M., “A Second-Order Logic in which Variables Range over Relations with Complete First-Order Types”, 2010 XXIX International Conference of the Chilean Computer Science Society (SCCC) IEEE, p. 270-279, 2010.
[10] Libkin, L., “Elements of Finite Model Theory”, Springer, 2004.
[11] J. M. Turull-Torres, “Relational Databases and Homogeneity in Logics with Counting”, Acta Cybernetica, Vol 17, number 3, pp. 485-511, 2006.
[2] Abiteboul, S., Vianu, V., “Generic Computation and its Complexity”, STOC 1991.
[3] Abiteboul, S., Vardi, M., Vianu, V., “Computing with Infinitary Logic”, Theoretical Computer Science 149, 1, pp. 101-128, 1995.
[4] Abiteboul, S., Vardi, M. Y., Vianu, V., “Fixpoint logics, relational machines, and computational complexity”, JACM 44 (1997) 30-56.
[5] Dawar, A., “A restricted second order logic for finite structures”. Information and Computation 143 (1998) 154-174.
[6] Fagin, R., “Generalized First-Order Spectra and Polynomial-Time Recognizable Sets”, in “Complexity of Computations”, edited by R. Karp, SIAM-AMS Proc., American Mathematical Society, Providence, RI, pp. 27–41, 1974.
[7] F. A. Ferrarotti, A. L. Paoletti, J. M. Turull-Torres, “Redundant Relations in Relational Databases: A Model Theoretic Perspective”, Journal of Universal Computer Science, Vol. 16, No. 20, pp. 2934-2955, 2010. http://www.jucs.org/jucs 16 20/redundant relations in relational
[8] Ferrarotti, F. A., Turull-Torres, J. M., “The Relational Polynomial-Time Hierarchy and Second-Order Logic”, invited for “Semantics in Databases”, edited by K-D. Schewe and B. Thalheim, Springer LNCS 4925, 29 pages, 2008.
[9] Grosso, A. L., Turul-Torres J. M., “A Second-Order Logic in which Variables Range over Relations with Complete First-Order Types”, 2010 XXIX International Conference of the Chilean Computer Science Society (SCCC) IEEE, p. 270-279, 2010.
[10] Libkin, L., “Elements of Finite Model Theory”, Springer, 2004.
[11] J. M. Turull-Torres, “Relational Databases and Homogeneity in Logics with Counting”, Acta Cybernetica, Vol 17, number 3, pp. 485-511, 2006.
Downloads
Published
2015-11-01
How to Cite
Turull Torres, J. M. (2015). Capturing relational NEXPTIME with a fragment of existential third order logic. Journal of Computer Science and Technology, 15(02), p. 87–92. Retrieved from https://journal.info.unlp.edu.ar/JCST/article/view/549
Issue
Section
Original Articles
