Paper Info
Title
Wreath Products of Distributive Forest Algebras.
Abstract
It is an open problem whether definability in Propositional Dynamic Logic (PDL) on forests is decidable. Based on an algebraic characterization by Bojanczyk, 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.
Year
DOI
Venue
2018
10.1145/3209108.3209158
LICS'18: PROCEEDINGS OF THE 33RD ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE
Field
DocType
Citations 
Distributive property,Discrete mathematics,Categorical quantum mechanics,Algebraic number,Open problem,Quantum computer,Decidability,Dynamic logic (digital electronics),Iterated function,Mathematics
Conference
0
PageRank 
References 
Authors
0.34
9
3
Name
Order
Citations
PageRank
Michael Hahn1383.60
Andreas Krebs2218.20
Howard Straubing352860.92