Parameterized Complexity of Propositional Inclusion and Independence Logic

&
In Helle Hvid Hansen, Andre Scedrov & Ruy J. G. B. De Queiroz (eds.), Logic, Language, Information, and Computation: 29th International Workshop, WoLLIC 2023, Halifax, NS, Canada, July 11–14, 2023, Proceedings. Springer Nature Switzerland. pp. 274-291 (2023)
  Copy   BIBTEX

Abstract

We give a comprehensive account on the parameterized complexity of model checking and satisfiability of propositional inclusion and independence logic. We discover that for most parameterizations the problems are either in FPT or paraNP-complete.

Categories

Add categories

Keywords

Reprint years

DOI

10.1007/978-3-031-39784-4_17

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,854

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

Logic, Language, Information, and Computation: 29th International Workshop, WoLLIC 2023, Halifax, NS, Canada, July 11–14, 2023, Proceedings.Helle Hvid Hansen, Andre Scedrov & Ruy J. G. B. De Queiroz (eds.) - 2023 - Springer Nature Switzerland.
An Axiom System for Basic Hybrid Logic with Propositional Quantifiers.Patrick Blackburn, Torben Braüner & Julie Lundbak Kofod - 2023 - In Helle Hvid Hansen, Andre Scedrov & Ruy J. G. B. De Queiroz (eds.), Logic, Language, Information, and Computation: 29th International Workshop, WoLLIC 2023, Halifax, NS, Canada, July 11–14, 2023, Proceedings. Springer Nature Switzerland. pp. 118-134.
Correction to: Decidability of Modal Logics of Non-k-Colorable Graphs.Ilya Shapirovsky - 2023 - In Helle Hvid Hansen, Andre Scedrov & Ruy J. G. B. De Queiroz (eds.), Logic, Language, Information, and Computation: 29th International Workshop, WoLLIC 2023, Halifax, NS, Canada, July 11–14, 2023, Proceedings. Springer Nature Switzerland.
Bisimulations Between Verbrugge Models and Veltman Models.Tin Perkov - 2023 - In Helle Hvid Hansen, Andre Scedrov & Ruy J. G. B. De Queiroz (eds.), Logic, Language, Information, and Computation: 29th International Workshop, WoLLIC 2023, Halifax, NS, Canada, July 11–14, 2023, Proceedings. Springer Nature Switzerland. pp. 305-317.
Effective Skolemization.Matthias Baaz & Anela Lolić - 2023 - In Helle Hvid Hansen, Andre Scedrov & Ruy J. G. B. De Queiroz (eds.), Logic, Language, Information, and Computation: 29th International Workshop, WoLLIC 2023, Halifax, NS, Canada, July 11–14, 2023, Proceedings. Springer Nature Switzerland. pp. 69-82.
Quantitative Global Memory.Sandra Alves, Delia Kesner & Miguel Ramos - 2023 - In Helle Hvid Hansen, Andre Scedrov & Ruy J. G. B. De Queiroz (eds.), Logic, Language, Information, and Computation: 29th International Workshop, WoLLIC 2023, Halifax, NS, Canada, July 11–14, 2023, Proceedings. Springer Nature Switzerland. pp. 53-68.
Learning Context-Free Grammars from Positive Data and Membership Queries.Makoto Kanazawa - 2023 - In Helle Hvid Hansen, Andre Scedrov & Ruy J. G. B. De Queiroz (eds.), Logic, Language, Information, and Computation: 29th International Workshop, WoLLIC 2023, Halifax, NS, Canada, July 11–14, 2023, Proceedings. Springer Nature Switzerland. pp. 3-18.
Validity in Choice Logics.Robert Freiman & Michael Bernreiter - 2023 - In Helle Hvid Hansen, Andre Scedrov & Ruy J. G. B. De Queiroz (eds.), Logic, Language, Information, and Computation: 29th International Workshop, WoLLIC 2023, Halifax, NS, Canada, July 11–14, 2023, Proceedings. Springer Nature Switzerland. pp. 211-226.
Decidability of Modal Logics of Non-k-Colorable Graphs.Ilya Shapirovsky - 2023 - In Helle Hvid Hansen, Andre Scedrov & Ruy J. G. B. De Queiroz (eds.), Logic, Language, Information, and Computation: 29th International Workshop, WoLLIC 2023, Halifax, NS, Canada, July 11–14, 2023, Proceedings. Springer Nature Switzerland. pp. 351-361.
A Separation Logic with Histories of Epistemic Actions as Resources.Hans van Ditmarsch, Didier Galmiche & Marta Gawek - 2023 - In Helle Hvid Hansen, Andre Scedrov & Ruy J. G. B. De Queiroz (eds.), Logic, Language, Information, and Computation: 29th International Workshop, WoLLIC 2023, Halifax, NS, Canada, July 11–14, 2023, Proceedings. Springer Nature Switzerland. pp. 161-177.

Analytics

Added to PP
2023-08-31

Downloads
3 (#1,854,928)

6 months
2 (#1,694,052)

Historical graph of downloads
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