Synchronous versions of regulated grammars : generative power and linguistic applications

• Autorzy: Horáček P. , Meduna A.
• Języki publikacji: PL

Abstrakty

EN

This paper introduces the notion of new synchronous grammars as systems consisting of two context-free grammars with linked rules instead of linked nonterminals. Further, synchronous versions of regulated grammars, specifically, matrix grammars and scattered context grammars, are discussed. From a theoretical point of view, this paper discusses the power of these synchronous grammars. It demonstrates the following main results. First, if we synchronize context-free grammars by linking rules, the grammar generates the languages defined by matrix grammars. Second, if we synchronize matrix grammars by linking matrices, the generative power remains unchanged. Third, synchronous scattered context grammars generate the class of recursively enumerable languages. From a more practical viewpoint, this paper presents linguistic application prospects. The focus is on natural language translation between Japanese and English.

Słowa kluczowe

EN

regulated grammar; synchronous grammar; generative power; natural language translation

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2012
• Tom: Vol. 24, No. 3
• Strony: 175--190
• Opis fizyczny: Bibliogr. 12 poz., rys.

Twórcy

autor

Horáček P.

autor

Meduna A.

• Formal Model Research Group, Department of Information Systems, Faculty of Information Technology, Brno University of Technology, Božetechova 1/2, 612 66 Brno, Czech Republic,

Bibliografia

• 1. A.V. Aho, J.D. Ullman: Syntax directed translations and the pushdown assembler. In Journal of Computer and System Sciences Volume 3, 1969, p. 37-56.
• 2. O. Bojar, M. Cˇmejrek: Mathematical model of tree transformations. Project Euroma-trix Deliverable 3.2, Charles University, Prague, 2007.
• 3. D. Chiang: An introduction to synchronous grammars [online]. Part of a tutorial given at 44th Annual Meeting of the Association for Computational Linguistics, 2006, http://www.isi.edu/ chiang/papers/synchtut.pdf
• 4. J. Dassow, Gh. Paun: Regulated Rewriting in Formal Language Theory. Springer, 1989,ISBN 3-540-51414-7.
• 5. J. Hajic: Disambiguation of Rich Inflection: Computational Morphology of Czech. Wisconsin Center for Pushkin Studies, Karolinum, 2004.
• 6. P. Horácek, A. Meduna: Regulated rewriting in natural language translation, In: 7th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, Brno,CZ, 2011, ISBN 978-80-214-4305-1, p. 35-42.
• 7. M. Khalilov, J.A.R. Fonollosa: N-gram-based statistical machine translation versus syntax augmented machine translation: comparison and system combination. In: Proceedings of the 12th Conference of the European Chapter of the Association for Computational Linguistics, EACL ’09, Stroudsburg, PA, USA, 2009, p. 424-432.
• 8. P.M. Lewis, R.E. Stearns: Syntax-directed transduction. In Journal of the ACM Volume 15, 1968, p. 465-488.
• 9. A. Meduna: Automata and Languages: Theory and Applications. Springer, 2005, ISBN 1-85233-074-0, 892 p.
• 10. A. Meduna, J. Techet: Scattered Context Grammars and their Applications. WIT Press, UK, 2010, ISBN 978-1-84564-426-0, 224 p.
• 11. R. Mitkov (ed.): The Oxford Handbook of Computational Linguistics. Oxford University Press, 2004, ISBN 978-0-19-927634-9.
• 12.G. Rozenberg, A. Salomaa: Handbook of Formal Languages: Volume I. Springer, 1997.