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: | ![]() |
