The Copying Power of Well-Nested Multiple Context-Free Grammars

1. Arnold, A., Dauchet, M.: Un théorem de duplication pour les forêts algébriques. Journal of Computer and System Science 13, 223–244 (1976)

   MATH  MathSciNet  Google Scholar 

2. Ehrenfeucht, A., Rozenberg, G.: On some context-free languages that are not deterministic ET0L languages. R.A.I.R.O. Informatique théorique/Theoretical Computer Science 11, 273–291 (1977)

   MATH  MathSciNet  Google Scholar 

3. Engelfriet, J., Rozenberg, G., Slutzki, G.: Tree transducers, L systems, and two-way machines. Journal of Computer and System Sciences 20, 150–202 (1980)

   Article  MATH  MathSciNet  Google Scholar 

4. Engelfriet, J., Skyum, S.: Copying theorems. Information Processing Letters 4, 157–161 (1976)

   Article  MATH  MathSciNet  Google Scholar 

5. Fisher, M.J.: Grammars with Macro-Like Productions. Ph.D. thesis, Harvard University (1968)

   Google Scholar 

6. Hayashi, T.: On derivation trees of indexed gramamrs —an extension of the uvwxy-theorem—. Publications of the Research Institute for Mathematical Sciences 9, 61–92 (1973)

   Article  Google Scholar 

7. Hotz, G., Pitsch, G.: On parsing coupled-context-free languages. Thoretical Computer Science 161, 205–253 (1996)

   Article  MATH  MathSciNet  Google Scholar 

8. Ito, M., Katsura, M.: Context-free languages consisting of non-primitive words. International Journal of Computer Mathematics 40, 157–167 (1991)

   Article  MATH  Google Scholar 

9. Joshi, A.K.: Tree adjoining grammars: How much context-sensitivity is required to provide reasonable structural descriptions? In: Dowty, D.R., Karttunen, L., Zwicky, A.M. (eds.) Natural Language Parsing: Psychological, Computational and Theoretical Perspectives, pp. 206–250. Cambridge University Press, Cambridge (1985)

   Chapter  Google Scholar 

10. Kanazawa, M.: The convergence of well-nested mildly context-sensitive grammar formalisms. In: An invited talk given at the 14th Conference on Formal Grammar, Bordeaux, France (July 2009), http://research.nii.ac.jp/~kanazawa/

11. Kanazawa, M.: The pumping lemma for well-nested multiple context-free languages. In: Diekert, V., Nowotka, D. (eds.) Developments in Language Theory: 13th International Conference, DLT 2009, pp. 312–325. Springer, Berlin (2009)

    Google Scholar 

12. Kuhlmann, M.: Dependency Structures and Lexicalized Grammars. Ph.D. thesis, Saarland University (2007)

    Google Scholar 

13. Michaelis, J.: An additional observation on strict derivational minimalism. In: Rogers, J. (ed.) Proceedings of FG-MoL 2005: The 10th conference on Formal Grammar and the 9th Meeting on Mathematics of Language, pp. 101–111. CSLI Publications, Stanford (2009)

    Google Scholar 

14. Rambow, O., Satta, G.: Independent parallelism in finite copying parallel rewriting systems. Theoretical Computer Science 223, 87–120 (1999)

    Article  MATH  MathSciNet  Google Scholar 

15. Rozoy, B.: The Dyck language D′₁ ^∗ is not generated by any matrix grammar of finite index. Information and Computation 74, 64–89 (1987)

    Article  MATH  MathSciNet  Google Scholar 

16. Satta, G.: Trading independent for synchronized parallelism in finite copying parallel rewriting systems. Journal of Computer and System Sciences 56, 27–45 (1998)

    Article  MATH  MathSciNet  Google Scholar 

17. Seki, H., Kato, Y.: On the generative power of multiple context-free grammars and macro grammars. IEICE Transactions on Information and Systems E91–D, 209–221 (2008)

    Article  Google Scholar 

18. Seki, H., Matsumura, T., Fujii, M., Kasami, T.: On multiple context-free grammars. Theoretical Computer Science 88, 191–229 (1991)

    Article  MATH  MathSciNet  Google Scholar 

19. Shallit, J.: A Second Course in Formal Langauges and Automata Theory. Cambridge University Press, Cambridge (2009)

    Google Scholar 

20. Staudacher, P.: New frontiers beyond context-freeness: DI-grammars and DI-automata. In: 6th Conference of the European Chapter of the Association for Computational Linguistics (EACL ’93), pp. 358–367 (1993)

    Google Scholar 

21. Vijay-Shanker, K., Weir, D.J., Joshi, A.K.: Characterizing structural descriptions produced by various grammatical formalisms. In: 25th Annual Meeting of the Association for Computational Linguistics, pp. 104–111 (1987)

    Google Scholar 

Download references