Special Issue: 21st International Conference on Implementation and Application of Automata (CIAA 2016)No Access

Regular Approximation of Weighted Linear Context-Free Tree Languages

Markus Teichmann

Markus Teichmann

Department of Computer Science, Technische Universität Dresden, 01062 Dresden, Germany

E-mail Address: markus.teichmann@mailbox.tu-dresden.de

Financially supported by DFG Graduiertenkolleg 1763 (QuantLA).

Search for more papers by this author

https://doi.org/10.1142/S0129054117400056Cited by:0 (Source: Crossref)

Abstract

We show how to train a weighted regular tree grammar such that it best approximates a weighted linear context-free tree grammar concerning the Kullback–Leibler divergence between both grammars. Furthermore, we construct a regular tree grammar that approximates the tree language induced by a context-free tree grammar.

This work is an extension of [6].

Communicated by Yo-Sub Han and Kai Salomaa

Keywords:

References

1. A. Corazza and G. Satta, Probabilistic context-free grammars estimated from infinite distributions, IEEE Trans. Pattern Anal. Mach. Intell. 29(8) (2007) 1379–1393. Crossref, Web of Science, Google Scholar
2. J. Engelfriet, Context-free grammars with storage, Tech. Rep. 86–11, University of Leiden (1986). Republished 2014 (arXiv:1408.0683). Google Scholar
3. M. Fischer, Grammars with macro-like productions, PhD thesis, Harvard University, Massachusetts (1968). Google Scholar
4. F. Gécseg and M. Steinby, Tree Automata (Akadémiai Kiadó, Budapest, 1984). Re-issued 2015: arXiv:1509.06233. Google Scholar
5. I. Guessarian, Pushdown tree automata, Math. Syst. Theory 16(1) (1983) 237–263. Crossref, Google Scholar
6. A. Joshi and Y. Schabes, Tree-adjoining grammars, Handbook of Formal Languages, eds. G. Rozenberg and A. Salomaa (Springer-Verlag, 1997), pp. 69–123. Crossref, Google Scholar
7. S. Kepser and U. Mönnich, Closure properties of linear context-free tree languages with an application to optimality theory, Theoretical Comp. Sci. 354(1) (2006) 82–97. Crossref, Web of Science, Google Scholar
8. S. Kepser and J. Rogers, The equivalence of tree adjoining grammars and monadic linear context-free tree grammars, J. Log., Lang. Inf. 20(3) (2011) 361–384. Crossref, Google Scholar
9. S. Kullback and R. A. Leibler, On information and sufficiency, Ann. Math. Statist. 22(1) (1951) 79–86. Crossref, Web of Science, Google Scholar
10. A. Maletti and J. Engelfriet, Strong lexicalization of tree adjoining grammars, Proc. 50th Ann. Meeting ACL, eds. H. Li, C.-Y. Lin, M. Osborne, G. G. Lee and J. C. Park (2012), pp. 506–515. Google Scholar
11. M.-J. Nederhof, Regular approximation of CFLs: A grammatical view, Adv. Prob. and Other Parsing Technol., eds. H. Bunt and A. Nijholt, Text, Speech Lang. Technol. 16 (Springer, 2000), pp. 221–241. Crossref, Google Scholar
12. M.-J. Nederhof, A general technique to train language models on language models, Comput. Linguist. 31(2) (2005) 173–186. Crossref, Web of Science, Google Scholar
13. M.-J. Nederhof, Weighted parsing of trees, Proc. 11th Int. Conf. Parsing Technol. (ACL, 2009), pp. 13–24. Google Scholar
14. M.-J. Nederhof, M. Teichmann and H. Vogler, Non-self-embedding linear context-free tree grammars generate regular tree languages, J.Automata, Lang. Comb. 21(3) (2016) 203–246. Google Scholar
15. M.-J. Nederhof and H. Vogler, Synchronous context-free tree grammars, Proc. of 11th Int. Workshop on Tree Adjoin. Gramm. and Relat. Formalisms (2012), pp. 55–63. Google Scholar
16. J. Osterholzer, Pushdown machines for weighted context-free tree translation, Proc. of 19th Int. Conf. on Implement. and Appl. of Automata, CIAA (2014). Google Scholar
17. W. C. Rounds, Mappings and grammars on trees, Math. Syst. Theory 4(3) (1970) 257–287. Crossref, Google Scholar
18. W. C. Rounds, Tree-oriented proofs of some theorems on context-free and indexed languages, Proc. of Second Ann. ACM Symp. on Theory of Comput. STOC (ACM, New York, NY, USA, 1970), pp. 109–116. Google Scholar
19. Y. Schabes, A. Abeille and A. K. Joshi, Parsing strategies with ‘lexicalized’ grammars: Application to tree adjoining grammars, Proc. 12th Conf. Comput. Ling., COLING 2 (ACL, 1988), pp. 578–583. Google Scholar
20. S. Shieber, Evidence against the context-freeness of natural language, Linguist. and Philos. 8 (1985) 333–343. Crossref, Web of Science, Google Scholar
21. M. Teichmann, Regular approximation of weighted linear nondeleting context-free tree languages, Proc. 21st Int. Conf. Impl. Appl. Automata, eds. Y.-S. Han and K. Salomaa, Lecture Notes in Comput. Sci. 9705 (Springer, 2016), pp. 273–284. Google Scholar