Copyright © 2008 The Institute of Electronics, Information and Communication Engineers
Special Section on Foundations of Computer Science -- Papers -- Formal Language Theory |
On the Generative Power of Multiple Context-Free Grammars and Macro Grammars
1 The author is with the Graduate School of Information Science, Nara Institute of Science and Technology, Ikoma-shi, 630–0192 Japan. E-mail: seki{at}is.naist.jp, 2 The author is with Bioinformatics Center, Institute for Chemical Research, Kyoto University, Uji-shi, 611–0011 Japan.
Several grammars of which generative power is between context-free grammar and context-sensitive grammar were proposed. Among them are macro grammar and tree adjoining grammar. Multiple context-free grammar is also a natural extension of context-free grammars, and is known to be stronger in its generative power than tree adjoining grammar and yet to be recognizable in polynomial time. In this paper, the generative power of several subclasses of variable-linear macro grammars and that of multiple context-free grammars are compared in details.
Key Words: multiple context-free grammar, macro grammar, context-free tree grammar, generative power, linearity
Manuscript received April 2, 2007. Manuscript revised June 28, 2007.
Reference
[1] N. Abe and H. Mamitsuka, "Predicting protein secondary structure using stochastic tree grammars," Mach. Learn., vol.29, pp.275–301, 1997. [2] A.V. Aho, "Indexed grammars – An extension of the context-free grammars," J. ACM, vol.15, pp.647–671, 1968. [3] A. Condon, "Problems on RNA secondary structure prediction and design," ICALP2003, LNCS 2719, pp.22–32, 2003. [4] R. Durbin, S. Eddy, A. Krogh, and G. Mitchison, Biological Sequence Analysis, Cambridge University Press, 1998. [5] J. Engelfriet and G. Rozenberg, "Tree transducers, L systems, and two-way machines," J. Comput. Syst. Sci., vol.20, pp.150–202, 1980. [6] M.J. Fischer, Grammars with Macro-like Productions, Ph.D. Thesis, Harvard University, 1968, also in 9th IEEE Sympo. on Switching and Automata Theory, 1968. [7] A. Fujiyoshi and T. Kasai, "Spinal-formed context-free tree grammars," Theor. Comput. Syst., vol.33, no.1, pp.59–83, 2000. [8] A.K. Joshi, L. Levy, and M. Takahashi, "Tree adjunct grammars," J. Comput. Syst. Sci., vol.10, no.1, pp.136–163, 1975. [9] A.K. Joshi and Y. Schabes, "Tree adjoining grammars," in Handbook of Formal Languages, vol.3 (Beyond Words), eds. G. Rozenberg and A. Salomaa, pp.69–123, Springer, 1997. [10] T. Kasami, H. Seki, and M. Fujii, "Generalized context-free grammar and multiple context-free grammar," IEICE Trans. Inf. & Syst. (Japanese Edition), vol.J71-D, no.5, pp.758–765, May 1988. [11] T. Kasami, H. Seki, and M. Fujii, "On the membership problem for head languages and multiple context-free languages," IEICE Trans. Inf. & Syst. (Japanese Edition), vol.J71-D, no.6, pp.935–941, June 1988. [12] Y. Kato, H. Seki, and T. Kasami, "On the generative power of grammars for RNA secondary structure," IEICE Trans. Inf. & Syst., vol.E88-D, no.1, pp.53–64, Jan. 2005. [13] Y. Kato, H. Seki, and T. Kasami, "RNA pseudoknotted structure prediction using stochastic multiple context-free grammar," IPSJ Trans. Bioinformatics, vol.47, SIG17(TBIO1), pp.12–21, 2006. [14] S. Kepser and U. Mönnich, "Closure properties of linear context-free tree languages with an application to optimality theory," Theor. Comput. Sci., vol.354, pp.82–97, 2006. [15] M. Latteux, "Substitutions dans les EDT0L-systèmes ultralinéaires," Information & Control, vol.42, pp.194–260, 1979. [16] A. Mateescu and A. Salomaa, "Aspects of classical language theory," in Handbook of Formal Languages, vol.1 (Word, Language, Grammar), eds. G. Rozenberg and A. Salomaa, pp.175–251, Springer, 1997. [17] H. Matsui, K. Sato, and Y. Sakakibara, "Pair stochastic tree adjoining grammars for aligning and predicting pseudoknot RNA structures," Bioinformatics, vol.21, no.11, pp.2611–2617, 2005. [18] O. Rambow and G. Satta, "A two-dimensional hierarchy for parallel rewriting systems," IRCS Report 94-02, Institute for Research in Cognitive Science, University of Pennsylvania, 1994. [19] O. Rambow and G. Satta, "Independent parallelism in finite copying parallel rewriting systems," Theor. Comput. Sci., vol.223, pp.87–120, 1999. [20] E. Rivas and S. Eddy, "The language of RNA: A formal grammar that includes pseudoknots," Bioinformatics, vol.16, no.4, pp.334–340, 2000. [21] W.C. Rounds, "Mappings and grammars on trees," Mathematical Systems Theory, vol.4, no.3, pp.257–287, 1970. [22] W.C. Rounds, "Tree-oriented proofs of some theorems on context-free and indexed languages," 2nd Annual ACM Symposium on Theory of Computing (STOC), pp.109–116, 1970. [23] H. Seki and Y. Kato, "On the generative power of multiple context-free grammars and macro grammars," Information Science Technical Report, NAIST-IS-TR2006007, Nara Institute of Science and Technology, 2006. [24] H. Seki, T. Matsumura, M. Fujii, and T. Kasami, "On multiple context-free grammars," Theor. Comput. Sci., vol.88, pp.191–229, 1991. [25] S. Seki and S. Kobayashi, "A grammatical approach to the alignment of structure-annotated strings," IEICE Trans. Inf. & Syst., vol.E88-D, no.12, pp.2727–2737, Dec. 2005. [26] Y. Uemura, A. Hasegawa, S. Kobayashi, and T. Yokomori, "Tree adjoining grammars for RNA structure prediction," Theor. Comput. Sci., vol.210, pp.277–303, 1999. [27] D.J. Weir, Characterizing mildly context-sensitive grammar formalisms, Ph.D. Thesis, Department of Computer and Information Science, University of Pennsylvania, 1988. [28] D.J. Weir, "Linear context-free rewriting systems and deterministic tree-walking transducers," 30th Meeting of the Assoc. for Computational Linguistics (ACL92), pp.136–143, 1992.
CiteULike 
Connotea 
Del.icio.us What's this?
This Article 
Abstract
Full Text (PDF)
Alert me when this article is cited
Alert me if a correction is posted
Services
Email this article to a friend
Similar articles in this journal
Alert me to new issues of the journal
Add to My Personal Archive
Download to citation manager
Request Permissions
Google Scholar
Articles by SEKI, H.
Articles by KATO, Y.
Search for Related Content
Social Bookmarking
What's this?