# CYK Parsing over Distributed Representations
## 3 Preliminaries
### Encoding and Using Unary Rules
We also show how to implement D-CYK by means of a recurrent neural network, based on the unfolding of the input string into tokens that encode the search space of all possible constituents. Preliminary experiments show that, to some extent, D-CYK can simulate CYK in the new setting of distributed representations. In this work, we exploited holographic reduced representations, a specific distributed representation. In future work, we intend to explore alternative distributed representations, possibly using training, for use with our D-CYK algorithm. Neural networks are a tremendous opportunity to develop novel solutions for known tasks. Our proposal opens the avenue of revitalizing symbolic parsing methods in the framework of neural networks for NLP and for other areas working with parsing algorithms and grammars along with neural networks [31; 32]. In fact, D-CYK is the first step towards the definition of a \"completely distributed CYK algorithm\" that builds trees in distributed representations during the computation, and it fosters the definition of recurrent layers of CYK-informed neural networks. Conceptualization, F.M.Z. ; formal analysis, G.S. ; software, G.C. ; writing--original draft, F.M.Z. and G.S. All authors have read and agreed to the published version of the manuscript. This research received no external funding. The authors declare no conflict of interest. ## References

* Hopcroft et al. [2001] Hopcroft, J.E. ; Motwani, R.; Ullman, J.D. _Introduction to Automata Theory, Languages, and Computation_, 2 nd ed. ; Addison-Wesley: Reading, MA, USA, 2001. * Sippu and Soisalon-Soininen [1990] Sippu, S.; Soisalon-Soininen, E. _Parsing Theory. \(LR(k)\) and \(LL(k)\) Parsing_; Springer: Berlin, Germany, 1990; Volume 2. * Aho et al. [2006] Aho, A.V. ; Lam, M.S. ; Sethi, R.; Ullman, J.D. _Compilers: Principles, Techniques, and Tools_, 2 nd ed. ; Addison-Wesley Longman Publishing Co., Inc.: Reading, MA, USA, 2006. * Graham and Harrison [1976] Graham, S.L. ; Harrison, M.A. Parsing of General Context Free Languages. In _Advances in Computers_; Academic Press: New York, NY, USA, 1976; Volume 14, pp. 77-185. * Nederhof and Satta [2010] Nederhof, M.; Satta, G. Theory of Parsing. In _The Handbook of Computational Linguistics and Natural Language Processing_; Clark, A., Fox, C., Lappin, S., Eds. ; Wiley: Hoboken, NJ, USA, 2010; Chapter 4, pp. 105-130. * Cocke [1969] Cocke, J. _Programming Languages and Their Compilers: Preliminary Notes_; Courant Institute of Mathematical Sciences, New York University: New York, NY, USA, 1969. * Younger [1967] Younger, D.H. Recognition and parsing of context-free languages in time \(\mathcal{O}(n^{3})\). _Inf. Control_**1967**, _10_, 189-208. [CrossRef]
* Kasami [1965] Kasami, T. _An eFicient Recognition And Syntax-Analysis Algorithm For Context-Free Languages_; Technical Report; Air Force Cambridge Research Lab: Bedford, MA, USA, 1965. * Charniak [1996] Charniak, E. _Statistical Language Learning_, 1 st ed. ; MIT Press: Cambridge, MA, USA, 1996. * Huang and Chiang [2005] Huang, L.; Chiang, D. Better k-best Parsing. In Proceedings of the Ninth International Workshop on Parsing Technology, Association for Computational Linguistics, Vancouver, BC, Canada, 9-10 October 2005; pp. 53-64. * Goodfellow et al. [2016] Goodfellow, I.; Bengio, Y.; Courville, A. _Deep Learning_; The MIT Press: Cambridge, MA, USA, 2016. * Valiant [1975] Valiant, L.G. General Context-Free Recognition in Less Than Cubic Time. _J. Comput. Syst. Sci._**1975**, _10_, 308-315. [CrossRef]* Graham et al. (1980) Graham, S.L. ; Harrison, M.A. ; Ruzzo, W.L. An Improved Context-Free Recognizer. _ACM Trans. Program. Lang. Syst._**1980**, \(2\), 415-462. [CrossRef]
* Fanty (1986) Fanty, M.A. _Context-Free Parsing with Connectionist Networks_; American Institute of Physics Conference Series; American Institute of Physics: College Park, MD, USA, 1986; Volume 151, pp. 140-145. [CrossRef]
* Nijholt (1990) Nijholt, A. Meta-parsing in neural networks. In _Cybernetics and Systems '90_; Trappl, R., Ed.