FAQ
logo of Jagiellonian University in Krakow

New Grammar Systems and Their Application Perspectives

Publication date: 06.06.2014

Schedae Informaticae, 2013, Volume 22, pp. 47 - 68

https://doi.org/10.4467/20838476SI.13.005.2090

Authors

,
Petr Horáček
Brno University of Technology, Faculty of Information Technology, Czech Republic
All publications →
Alexander Meduna
Formal Language Research Group Department of Information Systems Faculty of Information Technology Brno University of Technology
All publications →

Titles

New Grammar Systems and Their Application Perspectives

Abstract

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 translation.

References

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.

Aho. A.V.; Compilers: principles, techniques, & tools, Pearson/AddisonWesley, 2007.

Allen J.; Natural language understanding (2nd edition), Benjamin/Cummings series in computer science. Benjamin/Cummings Pub. Co., 1995.

Bojar O., ˇCmejrek M.; Mathematical model of tree transformations. In: Project Euromatrix Deliverable 3.2, Charles University, Prague 2007.

Chiang. D.; An introduction to synchronous grammars. In: 44th Annual Meeting of the Association for Computational Linguistics, 2006.

Dassow J., P˘aun Gh.; Regulated Rewriting in Formal Language Theory, Springer-Verlag, Berlin 1989.

Ginsburg S.; Algebraic and Automata-Theoretic Properties of Formal Lan- guages, Elsevier Science Inc., New York, NY, USA, 1975.

Greibach S.A.; Remarks on blind and partially blind one-way multicounter ma- chines, Theor. Comput. Sci. 7, 1978, pp. 311–324.

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.

Hajiˇc J.; Disambiguation of Rich Inflection: Computational Morphology of Czech, Wisconsin Center for Pushkin Studies, Karolinum 2004.

Hopcroft J.E., Motwani R., Ullman J.D.; Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2000.

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.

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.

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.

Meduna A.; Automata and Languages: Theory and Applications, Springer, London 2000.

Meduna A., Techet J.; Scattered Context Grammars and their Applications, WIT Press, United Kingdom, 2010.

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.

Mitkov P. (ed.); The Oxford Handbook of Computational Linguistics, Oxford University Press, Oxford 2003.

Mohri M.; Finite-state transducers in language and speech processing, Comput. Linguist. 23(2), 1997, pp. 269–311.

Rozenberg G., Salomaa A. (eds.); Handbook of Formal Languages, Springer Verlag, Berlin 1997.

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.

Information

Information: Schedae Informaticae, 2013, Volume 22, pp. 47 - 68

Article type: Original article

Titles:

Polish:

New Grammar Systems and Their Application Perspectives

English:

New Grammar Systems and Their Application Perspectives

Authors

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

Published at: 06.06.2014

Article status: Open

Licence: None

Percentage share of authors:

Petr Horáček (Author) - 50%
Alexander Meduna (Author) - 50%

Article corrections:

-

Publication languages:

English

View count: 3131

Number of downloads: 1594

<p> New Grammar Systems and Their Application Perspectives</p>