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: |