Complexity of Grammar Induction for Quantum Types
arXiv:1404.3925 · doi:10.4204/EPTCS.172.16
Abstract
Most categorical models of meaning use a functor from the syntactic category to the semantic category. When semantic information is available, the problem of grammar induction can therefore be defined as finding preimages of the semantic types under this forgetful functor, lifting the information flow from the semantic level to a valid reduction at the syntactic level. We study the complexity of grammar induction, and show that for a variety of type systems, including pivotal and compact closed categories, the grammar induction problem is NP-complete. Our approach could be extended to linguistic type systems such as autonomous or bi-closed categories.
arXiv commentIn Proceedings QPL 2014, arXiv:1412.8102
References in corpus (5)
- A survey of graphical languages for monoidal categories
- Experimental Support for a Categorical Compositional Distributional Model of Meaning
- Lambek vs. Lambek: Functorial Vector Space Semantics and String Diagrams for Lambek Calculus
- Exploring Strategies for Classification of External Stimuli Using Statistical Features of the Plant Electrical Response
- Forward and Inverse Modelling Approaches for Prediction of Light Stimulus from Electrophysiological Response in Plants