FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
Wreath Products of Distributive Forest Algebras

Authors: Michael Hahn, Andreas Krebs and Howard Straubing

Paper Information

Title:Wreath Products of Distributive Forest Algebras
Authors:Michael Hahn, Andreas Krebs and Howard Straubing
Proceedings:LICS PDF files
Editors: Anuj Dawar and Erich Grädel
Keywords:Propositional Dynamic Logic, PDL, Logic on Trees, Forest Algebras, Wreath Products
Abstract:

ABSTRACT. It is an open problem whether definability in Propositional Dynamic Logic (PDL) on forests is decidable. Based on an al- gebraic characterization by Bojańczyk, et. al., (2012) in terms of forest algebras, Straubing (2013) described an approach to PDL based on a k-fold iterated distributive law. A proof that all languages satisfying such a k-fold iterated distributive law are in PDL would settle decidability of PDL. We solve this problem in the case k = 2: All languages recognized by forest algebras satisyfing a 2-fold iterated distributive law are in PDL. Furthermore, we show that this class is decidable. This provides a novel nontrivial decidable subclass of PDL, and demonstrates the viability of the proposed approach to deciding PDL in general.

Pages:9
Talk:Jul 10 12:00 (Session 54D)
Paper: