1732-3916 New Grammar Systems and Their Application Perspectives Horáček Petr author Meduna Alexander author Brno University of Technology, Faculty of Information Technology, Czech Republic Formal Language Research Group Department of Information Systems Faculty of Information Technology Brno University of Technology Correspondence to: Petr Horáček ihoracekp@fit.vutbr.cz Correspondence to: Alexander Meduna medunag@t.vutbr.cz 06 06 2014 Volume 22 2013 47 68 Copyright © 2014 2014 <p>This paper presents new grammar systems that describe transformations 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 translation.</p> 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, &amp; 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., ˇCmejrek 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 Lan- guages, Elsevier Science Inc., New York, NY, USA, 1975. 8 Greibach S.A.; Remarks on blind and partially blind one-way multicounter ma- chines, Theor. Comput. Sci. 7, 1978, pp. 311–324. 9 Gurari E.M., Ibarra O.H.; A note on finite-valued and finitely ambiguous trans- ducers, Theory of Computing Systems 16, 1983, pp. 61–66. 10 Hajiˇc 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´aˇcek 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´aˇcek P., Meduna A.; Synchronous versions of regulated grammars: Gen- erative 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 ver- sus 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 Compu- tational 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., ˇCerm´ak M., Hor´aˇcek 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.