Wreath Products of Distributive Forest Algebras

Autor:	Hahn, Michael, Krebs, Andreas, Straubing, Howard
Rok vydání:	2019
Předmět:	Computer Science - Formal Languages and Automata Theory
Druh dokumentu:	Working Paper
DOI:	10.1145/3209108.3209158
Popis:	It is an open problem whether definability in Propositional Dynamic Logic (PDL) on forests is decidable. Based on an algebraic characterization by Boja\'nczyk, 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 satisfying 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. Comment: Appeared in: LICS '18 Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, pages 512-520
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1911.03493 Zobrazit plný text záznamu View this record from Arxiv