Search Results

Documents authored by Padmanabha, Anantha

Document
DOI: 10.4230/LIPIcs.ICDT.2023.24
A Simple Algorithm for Consistent Query Answering Under Primary Keys

Authors: Diego Figueira, Anantha Padmanabha, Luc Segoufin, and Cristina Sirangelo

Published in: LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023)

Abstract
We consider the dichotomy conjecture for consistent query answering under primary key constraints. It states that, for every fixed Boolean conjunctive query q, testing whether q is certain (i.e. whether it evaluates to true over all repairs of a given inconsistent database) is either polynomial time or coNP-complete. This conjecture has been verified for self-join-free and path queries. We propose a simple inflationary fixpoint algorithm for consistent query answering which, for a given database, naively computes a set Δ of subsets of database repairs with at most k facts, where k is the size of the query q. The algorithm runs in polynomial time and can be formally defined as: 1) Initialize Δ with all sets S of at most k facts such that S⊧ q. 2) Add any set S of at most k facts to Δ if there exists a block B (i.e., a maximal set of facts sharing the same key) such that for every fact a ∈ B there is a set S' ∈ Δ contained in S ∪ {a}. The algorithm answers "q is certain" iff Δ eventually contains the empty set. The algorithm correctly computes certainty when the query q falls in the polynomial time cases of the known dichotomies for self-join-free queries and path queries. For arbitrary Boolean conjunctive queries, the algorithm is an under-approximation: the query is guaranteed to be certain if the algorithm claims so. However, there are polynomial time certain queries (with self-joins) which are not identified as such by the algorithm.
Cite as

Diego Figueira, Anantha Padmanabha, Luc Segoufin, and Cristina Sirangelo. A Simple Algorithm for Consistent Query Answering Under Primary Keys. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{figueira_et_al:LIPIcs.ICDT.2023.24,
  author =	{Figueira, Diego and Padmanabha, Anantha and Segoufin, Luc and Sirangelo, Cristina},
  title =	{{A Simple Algorithm for Consistent Query Answering Under Primary Keys}},
  booktitle =	{26th International Conference on Database Theory (ICDT 2023)},
  pages =	{24:1--24:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-270-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{255},
  editor =	{Geerts, Floris and Vandevoort, Brecht},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.24},
  URN =		{urn:nbn:de:0030-drops-177663},
  doi =		{10.4230/LIPIcs.ICDT.2023.24},
  annote =	{Keywords: consistent query answering, primary keys, conjunctive queries}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.70
Generalized Bundled Fragments for First-Order Modal Logic

Authors: Mo Liu, Anantha Padmanabha, R. Ramanujam, and Yanjing Wang

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
When we bundle quantifiers and modalities together (as in ∃x□, ◇∀x etc.) in first-order modal logic (FOML), we get new logical operators whose combinations produce interesting bundled fragments of FOML. It is well-known that finding decidable fragments of FOML is hard, but existing work shows that certain bundled fragments are decidable [Anantha Padmanabha et al., 2018], without any restriction on the arity of predicates, the number of variables, or the modal scope. In this paper, we explore generalized bundles such as ∀x∀y□, ∀x∃y◇ etc., and map the terrain with regard to decidability, presenting both decidability and undecidability results. In particular, we propose the loosely bundled fragment, which is decidable over increasing domains and encompasses all known decidable bundled fragments.
Cite as

Mo Liu, Anantha Padmanabha, R. Ramanujam, and Yanjing Wang. Generalized Bundled Fragments for First-Order Modal Logic. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 70:1-70:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.MFCS.2022.70,
  author =	{Liu, Mo and Padmanabha, Anantha and Ramanujam, R. and Wang, Yanjing},
  title =	{{Generalized Bundled Fragments for First-Order Modal Logic}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{70:1--70:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.70},
  URN =		{urn:nbn:de:0030-drops-168684},
  doi =		{10.4230/LIPIcs.MFCS.2022.70},
  annote =	{Keywords: bundled fragments, first-order modal logic, decidability, tableaux}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.30
Two variable fragment of Term Modal Logic

Authors: Anantha Padmanabha and R. Ramanujam

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
Term modal logics (TML) are modal logics with unboundedly many modalities, with quantification over modal indices, so that we can have formulas of the form Exists y Forall x (Box_x P(x,y) implies Diamond_y P(y,x)). Like First order modal logic, TML is also "notoriously" undecidable, in the sense that even very simple fragments are undecidable. In this paper, we show the decidability of one interesting fragment, that of two variable TML. This is in contrast to two-variable First order modal logic, which is undecidable.
Cite as

Anantha Padmanabha and R. Ramanujam. Two variable fragment of Term Modal Logic. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 30:1-30:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{padmanabha_et_al:LIPIcs.MFCS.2019.30,
  author =	{Padmanabha, Anantha and Ramanujam, R.},
  title =	{{Two variable fragment of Term Modal Logic}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{30:1--30:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.30},
  URN =		{urn:nbn:de:0030-drops-109741},
  doi =		{10.4230/LIPIcs.MFCS.2019.30},
  annote =	{Keywords: Term modal logic, satisfiability problem, two variable fragment, decidability}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2018.43
Bundled Fragments of First-Order Modal Logic: (Un)Decidability

Authors: Anantha Padmanabha, R Ramanujam, and Yanjing Wang

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

Abstract
Quantified modal logic is notorious for being undecidable, with very few known decidable fragments such as the monodic ones. For instance, even the two-variable fragment over unary predicates is undecidable. In this paper, we study a particular fragment, namely the bundled fragment, where a first-order quantifier is always followed by a modality when occurring in the formula, inspired by the proposal of [Yanjing Wang, 2017] in the context of non-standard epistemic logics of know-what, know-how, know-why, and so on. As always with quantified modal logics, it makes a significant difference whether the domain stays the same across possible worlds. In particular, we show that the predicate logic with the bundle "forall Box" alone is undecidable over constant domain interpretations, even with only monadic predicates, whereas having the "exists Box" bundle instead gives us a decidable logic. On the other hand, over increasing domain interpretations, we get decidability with both "forall Box" and "exists Box" bundles with unrestricted predicates, where we obtain tableau based procedures that run in PSPACE. We further show that the "exists Box" bundle cannot distinguish between constant domain and variable domain interpretations.
Cite as

Anantha Padmanabha, R Ramanujam, and Yanjing Wang. Bundled Fragments of First-Order Modal Logic: (Un)Decidability. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 43:1-43:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{padmanabha_et_al:LIPIcs.FSTTCS.2018.43,
  author =	{Padmanabha, Anantha and Ramanujam, R and Wang, Yanjing},
  title =	{{Bundled Fragments of First-Order Modal Logic: (Un)Decidability}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{43:1--43:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.43},
  URN =		{urn:nbn:de:0030-drops-99424},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.43},
  annote =	{Keywords: First-order modal logic, decidability, bundled fragments}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact