LIPIcs.STACS.2023.3.pdf
- Filesize: 384 kB
- 1 pages
Document
Logical Algorithmics: From Theory to Practice (Invited Talk)
Author
Moshe Y. Vardi 
-
Part of:
Volume:
40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2023-03-03
File
Document Identifiers
Author Details
Cite As Get BibTex
Moshe Y. Vardi. Logical Algorithmics: From Theory to Practice (Invited Talk). In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.STACS.2023.3
Abstract
The standard approach to algorithm development is to focus on a specific problem and develop for it a specific algorithm. Codd’s introduction of the relational model in 1970 included two fundamental ideas: (1) Relations provide a universal data representation formalism, and (2) Relational databases can be queried using first-order logic. Realizing these ideas required the development of a meta-algorithm, which takes a declarative query and executes it with respect to a database. In this talk, I will describe this approach, which I call Logical Algorithmics, in detail, and explore its profound ramification.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational complexity and cryptography
- Theory of computation → Design and analysis of algorithms
Keywords
- Logic
- Algorithms
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Jeffrey M. Dudek, Vu Phan, and Moshe Y. Vardi. ADDMC: weighted model counting with algebraic decision diagrams. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pages 1468-1476. AAAI Press, 2020. URL: https://ojs.aaai.org/index.php/AAAI/article/view/5505.
- Phokion G. Kolaitis and Moshe Y. Vardi. Conjunctive-query containment and constraint satisfaction. J. Comput. Syst. Sci., 61(2):302-332, 2000. URL: https://doi.org/10.1006/jcss.2000.1713.
- Guoqiang Pan and Moshe Y. Vardi. Symbolic techniques in satisfiability solving. J. Autom. Reason., 35(1-3):25-50, 2005. URL: https://doi.org/10.1007/s10817-005-9009-7.
- Vu H. N. Phan and Moshe Y. Vardi. DPO: dynamic-programming optimization on hybrid constraints. CoRR, abs/2205.08632, 2022. URL: https://doi.org/10.48550/arXiv.2205.08632.
- Moshe Y. Vardi. The complexity of relational query languages (extended abstract). In Harry R. Lewis, Barbara B. Simons, Walter A. Burkhard, and Lawrence H. Landweber, editors, Proceedings of the 14th Annual ACM Symposium on Theory of Computing, May 5-7, 1982, San Francisco, California, USA, pages 137-146. ACM, 1982. URL: https://doi.org/10.1145/800070.802186.
- Moshe Y. Vardi. On the complexity of bounded-variable queries. In Mihalis Yannakakis and Serge Abiteboul, editors, Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 22-25, 1995, San Jose, California, USA, pages 266-276. ACM Press, 1995. URL: https://doi.org/10.1145/212433.212474.