New Grammar Systems and Their Application Perspectives

• Autorzy: Horáček P. , Meduna A.

Identyfikatory

DOI

10.4467/20838476SI.13.005.2090

• Języki publikacji: EN

Abstrakty

EN

This paper presents new grammar systems that describe transfor- mations of syntactic structures. They represent two approaches: synchronous grammars and transducers. The systems consist of well-known models such as context-free grammars and finite automata. Particular attention is paid to synchronization of regulated grammars. The paper recalls formal definitions of the systems and discusses theoretical results regarding their generative and accepting power. The last part briefly introduces application perspectives in natural language translation, illustrated by examples of Czech-English trans- lation.

Słowa kluczowe

EN

synchronous grammars; regulated grammars; transducers; computational control; generative power; natural language translation

• Wydawca: Wydawnictwo Uniwersytetu Jagiellońskiego
• Czasopismo: Schedae Informaticae
• Rocznik: 2013
• Tom: Vol. 22
• Strony: 47--68
• Opis fizyczny: Bibliogr. 21 poz., rys.

Twórcy

autor

Horáček P.

• Brno University of Technology, Faculty of Information Technology, Božetéchova 1/2, 612 66 Brno, Czech Republic

autor

Meduna A.

• Brno University of Technology, Faculty of Information Technology, Božetéchova 1/2, 612 66 Brno, Czech Republic

Bibliografia

• [1] Abraham S.; Some questions of language theory. In: Proceedings of the 1965 conference on Computational linguistics, COLING ’65, Stroudsburg, PA, USA, 1965, Association for Computational Linguistics, pp. 1–11.
• [2] Aho. A.V.; Compilers: principles, techniques, & tools, Pearson/AddisonWesley, 2007.
• [3] Allen J.; Natural language understanding (2nd edition), Benjamin/Cummings series in computer science. Benjamin/Cummings Pub. Co., 1995.
• [4] Bojar O., Čmejrek M.; Mathematical model of tree transformations. In: Project Euromatrix Deliverable 3.2, Charles University, Prague 2007.
• [5] Chiang. D.; An introduction to synchronous grammars. In: 44th Annual Meeting of the Association for Computational Linguistics, 2006.
• [6] Dassow J., P˘aun Gh.; Regulated Rewriting in Formal Language Theory, Springer-Verlag, Berlin 1989.
• [7] Ginsburg S.; Algebraic and Automata-Theoretic Properties of Formal Languages, Elsevier Science Inc., New York, NY, USA, 1975.
• [8] Greibach S.A.; Remarks on blind and partially blind one-way multicounter machines, Theor. Comput. Sci. 7, 1978, pp. 311–324.
• [9] Gurari E.M., Ibarra O.H.; A note on finite-valued and finitely ambiguous transducers, Theory of Computing Systems 16, 1983, pp. 61–66.
• [10] Hajič J.; Disambiguation of Rich Inflection: Computational Morphology of Czech, Wisconsin Center for Pushkin Studies, Karolinum 2004.
• [11] Hopcroft J.E., Motwani R., Ullman J.D.; Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2000.
• [12] Horáček P., Meduna A.; Regulated rewriting in natural language translation. In: 7th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, Brno University of Technology, Brno, CZ, 2011, pp. 35–42.
• [13] Horáček P., Meduna A.; Synchronous versions of regulated grammars: Generative power and linguistic applications, Theoretical and Applied Informatics 24(3), 2012, pp. 175–190.
• [14] KhalilovM., Fonollosa J.A.R.; 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, Association for Computational Linguistics, Stroudsburg, PA, USA, 2009, pp. 424–432.
• [15] Meduna A.; Automata and Languages: Theory and Applications, Springer, London 2000.
• [16] Meduna A., Techet J.; Scattered Context Grammars and their Applications, WIT Press, United Kingdom, 2010.
• [17] Meduna A., Čermák M., Horaček P.; Rule-restricted automaton-grammar tranduscers: Power and linguistic applications, Mathematics for Applications 1(1),2012, pp. 13–35.
• [18] Mitkov P. (ed.); The Oxford Handbook of Computational Linguistics, Oxford University Press, Oxford 2003.
• [19] Mohri M.; Finite-state transducers in language and speech processing, Comput. Linguist. 23(2), 1997, pp. 269–311.
• [20] Rozenberg G., Salomaa A. (eds.); Handbook of Formal Languages, Springer-Verlag, Berlin 1997.
• [21] Zollmann A., Venugopal A.; Syntax augmented machine translation via chart parsing. In: Proceedings of the Workshop on Statistical Machine Translation, StatMT ’06, Association for Computational Linguistics, Stroudsburg, PA, USA, 2006, pp. 138–141.