Marco Kuhlmann, Andreas Maletti, and Lena Katharina Schiffer. The Tree-Generative Capacity of Combinatory Categorial Grammars. In Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pages 44:1–44:14, Mumbai, India, 2019.
The generative capacity of combinatory categorial grammars as acceptors of forests is investigated. It is demonstrated that the such obtained forests can also be generated by simple monadic context-free tree grammars. However, the subclass of pure combinatory categorial grammars cannot even accept all regular forests. Additionally, the forests accepted by combinatory categorial grammars with limited rule degrees are characterized: If only application rules are allowed, then they can accept only a proper subset of the regular forests, whereas they can accept exactly the regular forests once first degree composition rules are permitted.