What is symbolic rewriting?
Symbolic rewriting is the method to rewrite ground and nonground data from one to another form using rules.
This work investigates if the current neural architectures are adequate for learning symbolic rewriting. Two kinds of data sets are proposed for this research -- one based on automated proofs and the other being a synthetic set of polynomial terms. The experiments with use of the current neural machine translation models are performed and its results are discussed. Ideas for extending this line of research are proposed and its relevance is motivated.
Neural networks (NNs) turned out to be very useful in several domains. In particular, one of the most spectacular advances achieved with use of NNs has been natural language processing. One of the tasks in this domain is translation between natural languages – neural machine translation (NMT) systems established here the state-of-the-art performance. Recently, NMT produced first encouraging results in the autoformalization task BIBREF0, BIBREF1, BIBREF2, BIBREF3 where given an informal mathematical text in the goal is to translate it to its formal (computer understandable) counterpart. In particular, the NMT performance on a large synthetic -to-Mizar dataset produced by a relatively sophisticated toolchain developed for several decades BIBREF4 is surprisingly good BIBREF3, indicating that neural networks can learn quite complicated algorithms for symbolic data. This inspired us to pose a question: Can NMT models be used in the formal-to-formal setting? In particular: Can NMT models learn symbolic rewriting? The answer is relevant to various tasks in automated reasoning. For example, neural models could compete with symbolic methods such as inductive logic programming BIBREF5 (ILP) that have been previously experimented with to learn simple rewrite tasks and theorem-proving heuristics from large formal corpora BIBREF6. Unlike (early) ILP, neural methods can however easily cope with large and rich datasets, without combinatorial explosion. Our work is also an inquiry into the capabilities of NNs as such, in the spirit of works like BIBREF7.