acl acl2012 acl2012-139 acl2012-139-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Makoto Kanazawa ; Sylvain Salvati
Abstract: The language MIX consists of all strings over the three-letter alphabet {a, b, c} that contain an equal n-luemttebrer a olpfh occurrences }o tfh heaatch c olentttaeinr. We prove Joshi’s (1985) conjecture that MIX is not a tree-adjoining language.
Setsuo Arikawa, Takeshi Shinohara, and Akihiro Yamamoto. 1992. Learning elementary formal systems. Theoretical Computer Science, 95(1):97–1 13 . Emmon Bach. 1981 . Discontinuous constituents in generalized categorial grammars. In Victoria Burke and James Pustejovsky, editors, Proceedings of the 11th Annual Meeting of the North East Linguistic Society, pages 1–12. Emmon Bach. 1988. Categorial grammars as theories of language. In Richard T. Oehrle, Emmon Bach, and Deirdre Wheeler, editors, Categorial Grammars and Natural Language Structures, pages 17–34. D. Reidel, Dordrecht. Gerald Gazdar. 1988. Applicability of indexed grammars to natural languages. In U. Reyle and C. Rohrer, editors,NaturalLanguage Parsing andLinguistic Theories, pages 69–94. D. Reidel Publishing Company, Dordrecht. Robert Gilman. 2005. Formal languages and their application to combinatorial group theory. In Alexandre V. Borovik, editor, Groups, Languages, Algorithms, number 378 in Contemporary Mathematics, pages 1–36. American Mathematical Society, Providence, RI. Annius V. Groenink. 1997. Mild context-sensitivity and tuple-based generalizations of context-free grammar. Linguistics and Philosophy, 20:607–636. Aravind K. Joshi, Vijay K. Shanker, and David J. Weir. 1991 . The converence of mildly context-sensitive grammar formalisms. In Peter Sells, Stuart M. Shieber, and Thomas Wasow, editors, FoundationalIssues in Natural Language Processing, pages 3 1–81 . The MIT Press, Cambridge, MA. Aravind K. Joshi. 1985. Tree-adjoining grammars: How much context sensitivity is required to provide reasonable structural descriptions? In David Dowty, Lauri Karttunen, and Arnold M. Zwicky, editors, Natural Language Parsing, pages 206–250. Cambridge University Press, Cambridge. Markus Kracht. 2003 . The Mathematics of Language, volume 63 of Studies in Generative Grammar. Mouton de Gruyter, Berlin. William Marsh. 1985. Some conjectures on indexed languages. Paper presented to the Association for Symbolic Logic Meeting, Stanford University, July 15–19. Abstract appears in Journal of Symbolic Logic 5 1(3):849 (1986). Carl J. Pollard. 1984. Generalized Phrase Structure Grammars, Head Grammars, and Natural Language. Ph.D. thesis, Department of Linguistics, Stanford University. Kelly Roach. 1987. Formal properties of head grammars. In Alexis Manaster-Ramer, editor, Mathematics of Language, pages 293–347. John Benjamins, Amsterdam. Sylvain Salvati. 2011. MIX is a 2-MCFL and the word problem in Z2 is captured by the IO and the OI hierarchies. Technical report, INRIA. Hiroyuki Seki, Takashi Matsumura, Mamoru Fujii, and Tadao Kasami. 1991 . On multiple context free gram- K. Vijay-Shanker, David J. Weir, and Aravind K. Joshi. 1987. Characterizing structural descriptions produced by various grammatical formalisms. In 25th Annual Meeting ofthe Associationfor ComputationalLinguistics, pages 104–1 11. David J. Weir. 1988. Characterizing Mildly ContextSensitive Grammar Formalisms. Ph.D. thesis, University of Pennsylvania, Philadephia, PA. mars. Theoretical Computer Science, 88(2): 191–229. Raymond M. Smullyan. 1961 . Theory of Formal Systems. Princeton University Press, Princeton, NJ. K. Vijay-Shanker and D. J. Weir. 1994. The equivalence of four extensions of context-free grammars. Mathematical Systems Theory, 27:5 11–546. 674