Advances in Distributed Computing and Artificial Intelligence Journal

Salamanca University Press Journal

Linguistic Models at the Crossroads of Agents, Learning and Formal Languages

General information

Authors:
Leonor BECERRA-BONACHE, M. Dolores JIMÉNEZ LÓPEZ

DOI:
http://dx.doi.org/10.14201/ADCAIJ2014346888

Volume:
Regular Issue 3 (4), 2014

Keywords:

agents; learning; formal languages; linguistics

This paper aims at reviewing the most relevant linguistic applications developed in the intersection between three different fields: machine learning, formal language theory and agent technologies. On the one hand, we present some of the main linguistic contributions of the intersection between machine learning and formal languages, which constitutes a well-established research area known as Grammatical Inference. On the other hand, we present an overview of the main linguistic applications of models developed in the intersection between agent technologies and formal languages, such as colonies, grammar systems and eco-grammar systems. Our goal is to show how interdisciplinary research between these three fields can contribute to better understand how natural language is acquired and processed.

References

Adriaans, P., 1992. Language learning from a categorial perspective. Ph.D. thesis, University of Amsterdam.

Angluin, D., 1982. Inference of reversible languages. Journal of the Association for Computing Machinery, 29(3):741–765.

Angluin, D. and Becerra-Bonache, L., 2008. Learning Meaning Before Syntax. In ICGI: International Colloquium on Grammatical Inference, pages 1–14. Berlin.

Angluin, D. and Becerra-Bonache, L., 2010. A model of semantics and corrections in language learning. YALEU/DCS/TR-1425.

Angluin, D. and Becerra-Bonache, L., 2011. Effects of Meaning-Preserving Corrections on Language Learning. In CoNLL: International Conference on Computational Natural Language Learning, pages 97–105.

Bartlett, M. and Kazakov, D., 2004. The role of environment structure in multi-agent simulations of language evolution. In Proceedings of the Fourth Symposium on Adaptive Agents and Multi-Agent Systems. Springer.

Bayley, R., Cameron, R., and Lucas, C., 2013. The Oxford Handbook of Sociolinguistics. Oxford University Press, Oxford.

Becerra-Bonache, L., 2006. On the Learnability of Mildly Context-Sensitive Languages using Positive Data and Correction Queries. Ph.D. thesis, Rovira i Virgili University.

Becerra-Bonache, L., Case, J., Jain, S., and Stephan, F., 2010. Iterative learning of simple external contextual languages. Theoretical Computer Science, 411:2741–2756.

Becerra-Bonache, L. and Yokomori, T., 2004. Learning Mild Context-Sensitiveness: Toward Understanding Children’s Language Learning. In ICGI: International Colloquium on Grammatical Inference, pages 53–64.

Bel-Enguix, G. and Jiménez-López, M., 2008. Modelling dialogue as inter-action. International Journal of Speech Technology, 11(3/4):209–221.

Bel-Enguix, G., Jiménez-López, M., and Martín-Vide, C., 2009. Using finite-state methods for getting infinite languages: A preview. Romanian Journal of Information, Science and Technology, 12(2):125–137.

Bonnema, R., Bod, R., and Scha, R., 1997. A DOP Model for Semantic Interpretation. In 35th Annual Meeting of the Association for Computational Linguistics and 8th Conference of the European Chapter of the Association for Computational Linguistics, pages 159–167.

Bresnan, J., Kaplan, R., Peters, S., and Zaenen, A., 1987. Cross-Serial Dependencies in Dutch. In Savitch, W., Bach, E., Marsh, W., and Safran-Naveh, G., editors, The Formal Complexity of Natural Language, pages 286–319. D. Reidel, Dordrecht.

Brooks, R., 1990. Elephants don’t play chess. Robotics and Autonomous Systems, 6:3–15.

Cangelosi, A., 2007. Adaptive agent modeling of distributed language: investigations on the effects of cultural variation and internal action representations. Language Sciences, 29(5):633–549.

Cangelosi, A. and Parisi, D., 2001. Computer simulation: A new scientific approach to the study of language evolution. In Cangelosi, A. and Parisi, D., editors, Simulating the Evolution of Language, pages 3–28. Springer.

Casacuberta, F. and Vidal, E., 2007. Learning finite-state models for machine translation. Machine Learning, 66(1):69–91.

Chomsky, N., 1956. Three models for the description of language. IRE Transactions on Information Theory, 2(3):113–124.

Chouinard, M. and Clark, E., 2003. Adult Reformulations of Child Errors as Negative Evidence. Journal of Child Language, 30:637–669.

Christiansen, M. and Kirbi, S., 2003. Language evolution: Consensus and controversy. Trends in Cognitive Sciences, 7(7):300–307.

Clark, A. and Yoshinaka, R., 2014. Distributional learning of parallel multiple context-free grammars. Machine Learning, 96(1-2):5–31.

Csuhaj-Varjú, E., Dassow, J., Kelemen, J., and P˘aun, G., 1994. Grammar systems: A grammatical approach to distribution and cooperation. Gordon and Breach, London.

Csuhaj-Varjú, E., Kelemen, J., Kelemenová, A., and P˘aun, G., 1996. Eco-grammar systems: A grammatical framework for life-like interactions. Artificial Life, 3(1):1–28.

Culy, C., 1987. The Complexity of the Vocabulary of Bambara. In Savitch, W., Bach, E., Marsh, W., and Safran-Naveh, G., editors, The Formal Complexity of Natural Language, pages 349–357.

D’Ulizia, A., Ferri, F., and Grifoni, P., 2011. A survey of grammatical inference methods for natural language learning. Artificial Intelligence Review, 36(1):1–27.

García, P. and Vidal, E., 1990. Inference of k-Testable Languages in the Strict Sense and Application to Syntactic Pattern Recognition. IEEE Trans. Pattern Anal. Mach. Intell., 12(9):920–925.

Gazdar, G. and Pullum, G. K., 1985. Computationally Relevant Properties of Natural Languages and Their Grammars. New Generation Computing, 3:273–306.

Geeraerts, D. and Cuyckens, H., 2010. The Oxford Handbook of Cognitive Linguistics. Oxford University Press, Oxford.

Gold, E., 1967. Language identification in the limit. Information and Control, 10:447–474.

de la Higuera, C., 2010. Grammatical Inference: Learning Automata and Grammars. Cambridge University Press.

Horn, L. and Ward, G., 2005. The Handbook of Pragmatics. Blackwell, Oxford.

Jiménez-López, M., 2006. A grammar systems approach to natural language grammar. Linguistics and Philosophy, 29:419–454.

Jiménez-López, M., 2012. A grammar-based multi-agent system for language evolution. In Bajo Pérez, J. e. a., editor, Highlights on Practical Applications of Agents and Multiagent Systems, pages 45–52. Springer.

Joshi, A. K., 1985. How Much Context-Sensitivity is Required to Provide Reasonable Structural Descriptions: Tree Adjoining Grammars. In Dowty, D., Karttunen, L., and Zwicky, A., editors, Natural Language Parsing: Psychological, Computational and Theoretical Perspectives, pages 206–250. Cambridge University Press, New York, NY.

Joshi, A. K. and Schabes, Y., 1997. Tree-Adjoining Grammars. In Rozenberg, G. and Salomaa, A., editors, Handbook of Formal Languages, volume 3, pages 69–123. Springer-Verlag, Berlin.

Kelemen, J. and Kelemenová, A., 1992. A grammar-theoretic treatment of multiagent systems. Cybernetics and Systems, 23:621–633.

Kudlek, M., Martín-Vide, C., Mateescu, A., and Mitrana, V., 2002. Contexts and the concept of mild context-sensitivity. Linguistics and Philosophy, 26(6):703–725.

Langton, C., 1989. Artificial Life. In Langton, C., editor, Artificial Life, pages 1–47. Addison-Wesley.

Lappin, S., 1997. The Handbook of Contemporary Semantic Theory. Blackwell, Oxford.

Manaster-Ramer, A., 1999. Some Uses and Abuses of Mathematics in Linguistics. In Martín-Vide, C., editor, Issues in Mathematical Linguistics, pages 73–130. John Benjamins, Amsterdam.

Marcus, M. P., Santorini, B., and Marcinkiewicz, M. A., 1993. Building a Large Annotated Corpus of English: The Penn Treebank. Computational Linguistics, 19(2):313–330.

Newmeyer, F., 1997. Generative Linguistics: An Historical Perspective. Routledge, London.

Oates, T., Armstrong, T., Becerra-Bonache, L., and Atamas, M., 2006. Inferring grammars for mildly context sensitive languages in polynomial-time. In ICGI: International Colloquium on Grammatical Inference, pages 137–147.

Oncina, J. and García, P., 1992. Identifying Regular Languages In Polynomial Time. In Advances in Structural and Syntactic Pattern Recognition, pages 99–108. World Scientific.

Post, E., 1936. Finite combinatory processes-formulation. Journal of Symbolic Logic, 1:103–105.

Reitter, D. and Lebiere, C., 2010. Did social networks shape language evolution? A Multi-Agent Cognitive Simulation. In Proceedings of ACL 2010, pages 9–17. ACL.

Roach, K., 1987. Formal Porperties of Head Grammars. In Manaster-Ramer, A., editor, Mathematics of Language, pages 293–348. John Benjamins, Amsterdam.

Rozenberg, G. and Salomaa, A., 1997. Handbook of Dormal Languages. Springer, Berlin.

Sadock, J., 1991. Autolexical syntax. A theory of parallel grammatical representations. University of Chicago Press, Chicago.

Sakakibara, Y., 1992. Efficient learning of context-free grammars from positive structural examples. Information Processing Letters, 97:23–60.

Shieber, S., 1987. Evidence Against the Context-Freeness of Natural Languages. In Savitch, W., Bach, E., Marsh, W., and Safran-Naveh, G., editors, The Formal Complexity of Natural Language, pages 320–334. D. Reidel, Dordrecht.

Solan, Z., Horn, D., Ruppin, E., and Edelman, S., 2005. Unsupervised learning of natural languages. In Proceedings of the National Academy of Sciences of the USA, volume 102(33), pages 11629–11634.

Steedman, M., 1985. Dependency and Coordination in the grammar of Dutch and English. Language, 61:523–568.

Steels, L., 2006. How to do experiments in artificial language evolution and why. In Proceedings of the 6th International Conference on the Evolution of Language, pages 323–332.

Thue, A., 1906. Über unendliche Zeichenreihen. Norske Vid. Selsk. Skr., I Mat. Nat. Kl., Kristiania, 7:1–22.

Thue, A., 1912. Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske Vid. Selsk. Skr., I Mat. Nat. Kl., Kristiania, 1:1–67.

Turing, A., 1936. On computable numbers with an application to the Entscheidungsproblem. In Proceedings London Mathematical Society, pages 230–265.

Yoshinaka, R., 2009. Learning Mildly Context-Sensitive Languages with Multidimensional Substitutability from Positive Data. In ALT: International Conference on Algorithmic Learning Theory, pages 278–292.

van Zaanen, M., 2001. ABL: Alignment-Based Learning. CoRR, cs.LG/0104006.

van Zaanen, M., Roberts, A., and Atwell, E., 2004. A multilingual parallel parsed corpus as gold standard for grammatical inference evaluation. In In LREC: Workshop on The Amazing Utility of Parallel and Comparable Corpora, pages 58–61.

How to cite item?