EUVIMEDEUVIMED entdecken
Crossref

Limited-knowledge propositional announcement synthesis under Dalal revision: tight PH bounds, parameterized tractability and kernelization

Shuangmei Wang, Fengjie Sun

Journal of Logic and Computation · 29.04.2026 · 36 (4)

DOI: 10.1093/logcom/exag016 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Logic and Computation, online erschienen am 29.04.2026. Verfasst von Shuangmei Wang und 1 weiteren Autor:innen. Die Arbeit nennt 21 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study announcement synthesis under incomplete initial beliefs for multiple agents, instantiated with Dalal’s distance-based AGM revision. We introduce and formalize two semantics for the limited-knowledge propositional announcement problem: an optimistic variant (PAP$^{\exists }_{*_{D}}$), which requires success under some admissible completion per agent, and a robust variant (PAP$^{\forall }_{*_{D}}$), which requires success under all admissible completions. This distinction captures a fundamental trade-off in multi-agent coordination: optimism assumes favourable conditions, while robustness hedges against all contingencies. Our first contribution is a tight complexity classification revealing a precise quantifier-complexity correspondence: PAP$^{\exists }_{*_{D}}$ is $\varSigma _{2}^{\rm P}$-complete, while PAP$^{\forall }_{*_{D}}$ is $\varSigma _{3}^{\rm P}$-complete under extensional completion sets. The one-level gap confirms that robustness costs exactly one quantifier alternation in the polynomial hierarchy. The upper bounds follow from a small-announcement normal form—showing that effective coordination messages have bounded complexity—and NP-decidability of the distance-threshold predicate $\mathsf{Dist}_{\le }$. Second, we develop a parameterized tractability landscape that identifies when and why announcement synthesis becomes feasible despite worst-case intractability. We establish FPT algorithms parameterized by vocabulary size $k$ and announcement width $t$; FPT results for bounded completion-set sizes; and FPT in structural parameters (treewidth, backdoor size) via dynamic programming. The bounded-change variant is FPT in the $\ell _{1}$-budget $D=\sum _{i} d_{i}$. Five polynomial-time kernelization rules enable effective preprocessing. Conditional lower bounds under ETH and SETH identify unavoidable exponential dependencies. Finally, we discuss how alternative distance aggregations (average, maximum, Hausdorff) affect computational complexity, showing that our minimum-based framework provides the foundational ‘base case’ upon which more complex variants can build.

Zitieren

APA

Wang, S., & Sun, F. (2026). Limited-knowledge propositional announcement synthesis under Dalal revision: tight PH bounds, parameterized tractability and kernelization. Journal of Logic and Computation, 36(4). https://doi.org/10.1093/logcom/exag016

Vancouver

Wang S, Sun F. Limited-knowledge propositional announcement synthesis under Dalal revision: tight PH bounds, parameterized tractability and kernelization. Journal of Logic and Computation. 2026;36(4). doi:10.1093/logcom/exag016

BibTeX
@article{Wang2026,
  author = {Wang, Shuangmei and Sun, Fengjie},
  title = {Limited-knowledge propositional announcement synthesis under Dalal revision: tight PH bounds, parameterized tractability and kernelization},
  journal = {Journal of Logic and Computation},
  year = {2026},
  volume = {36},
  number = {4},
  doi = {10.1093/logcom/exag016}
}
Kostenlos starten →