The Expressive Power of Revised Datalog on Problems with Closure Properties

In Natasha Alechina, Andreas Herzig & Fei Liang (eds.), Logic, Rationality, and Interaction: 9th International Workshop, LORI 2023, Jinan, China, October 26–29, 2023, Proceedings. Springer Nature Switzerland. pp. 109-125 (2023)
  Copy   BIBTEX

Abstract

In this paper, we study the expressive power of revised Datalog on the problems that are closed under substructures. We show that revised Datalog cannot define all the problems that are in PTIME and closed under substructures. As a corollary, LFP cannot define all the extension-closed problems that are in PTIME.

Categories

Add categories

Keywords

Reprint years

DOI

10.1007/978-3-031-45558-2_9

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,590

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Hierarchies in transitive closure logic, stratified Datalog and infinitary logic.Erich Grädel & Gregory L. McColm - 1996 - Annals of Pure and Applied Logic 77 (2):169-199.
Connexivity Meets Church and Ackermann.Luis Estrada-González & Miguel Ángel Trejo-Huerta - 2023 - In Natasha Alechina, Andreas Herzig & Fei Liang (eds.), Logic, Rationality, and Interaction: 9th International Workshop, LORI 2023, Jinan, China, October 26–29, 2023, Proceedings. Springer Nature Switzerland. pp. 77-85.
An Inferential Theory of Causal Reasoning.Alexander Bochman - 2023 - In Natasha Alechina, Andreas Herzig & Fei Liang (eds.), Logic, Rationality, and Interaction: 9th International Workshop, LORI 2023, Jinan, China, October 26–29, 2023, Proceedings. Springer Nature Switzerland. pp. 1-16.
Indicative Conditionals in Awareness Framework.Tianyi Chu - 2023 - In Natasha Alechina, Andreas Herzig & Fei Liang (eds.), Logic, Rationality, and Interaction: 9th International Workshop, LORI 2023, Jinan, China, October 26–29, 2023, Proceedings. Springer Nature Switzerland. pp. 17-30.
Logic, Rationality, and Interaction: 9th International Workshop, LORI 2023, Jinan, China, October 26–29, 2023, Proceedings.Natasha Alechina, Andreas Herzig & Fei Liang (eds.) - 2023 - Springer Nature Switzerland.
A Temporal Logic for Successive Events.Yanjun Li & Jiajie Zhao - 2023 - In Natasha Alechina, Andreas Herzig & Fei Liang (eds.), Logic, Rationality, and Interaction: 9th International Workshop, LORI 2023, Jinan, China, October 26–29, 2023, Proceedings. Springer Nature Switzerland. pp. 176-189.
An Arrow-Based Dynamic Logic of Normative Systems and Its Decidability.Hans van Ditmarsch, Louwe Kuijer & Mo Liu - 2023 - In Natasha Alechina, Andreas Herzig & Fei Liang (eds.), Logic, Rationality, and Interaction: 9th International Workshop, LORI 2023, Jinan, China, October 26–29, 2023, Proceedings. Springer Nature Switzerland. pp. 63-76.
Hyperintensionality in Relevant Logics.Shawn Standefer - 2023 - In Natasha Alechina, Andreas Herzig & Fei Liang (eds.), Logic, Rationality, and Interaction: 9th International Workshop, LORI 2023, Jinan, China, October 26–29, 2023, Proceedings. Springer Nature Switzerland. pp. 238-250.
Cooperation Mechanisms for the Prisoner’s Dilemma with Bayesian Games.Wei Xiong - 2023 - In Natasha Alechina, Andreas Herzig & Fei Liang (eds.), Logic, Rationality, and Interaction: 9th International Workshop, LORI 2023, Jinan, China, October 26–29, 2023, Proceedings. Springer Nature Switzerland. pp. 284-291.
Belief Revision with Satisfaction Measure.Wei Zhao - 2023 - In Natasha Alechina, Andreas Herzig & Fei Liang (eds.), Logic, Rationality, and Interaction: 9th International Workshop, LORI 2023, Jinan, China, October 26–29, 2023, Proceedings. Springer Nature Switzerland. pp. 292-305.

Analytics

Added to PP
2023-10-25

Downloads
0

6 months
0

Historical graph of downloads

Sorry, there are not enough data points to plot this chart.
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references