Formal language theory

What’s so special about speech anyway?

The meeting of computation complexity theory and Natural language, amongst other things. Special sub fields: grammatical induction etc.

For now, see someone else writing about Chomsky Hierarchy.

Image from Hauser and Watumull (2016).


Autebert, Jean-Michel, Jean Berstel, and Luc Boasson. 1997. β€œContext-Free Languages and Pushdown Automata.” In Handbook of Formal Languages, Vol.Β 1, edited by Grzegorz Rozenberg and Arto Salomaa, 111–74. New York, NY, USA: Springer-Verlag New York, Inc.
Berstel, Jean, and Luc Boasson. 1990. β€œTransductions and Context-Free Languages.” In Handbook of Theoretical Computer Science, Vol. A: Algorithms and Complexity, edited by J. van Leeuwen, Albert R. Meyer, M. Nivat, Matthew Paterson, and D. Perrin, 1–278.
Berwick, Robert C., Kazuo Okanoya, Gabriel J.L. Beckers, and Johan J. Bolhuis. 2011. β€œSongs to Syntax: The Linguistics of Birdsong.” Trends in Cognitive Sciences 15 (3): 113–21.
Bolhuis, Johan J., Ian Tattersall, Noam Chomsky, and Robert C. Berwick. 2014. β€œHow Could Language Have Evolved?” PLoS Biol 12 (8): e1001934.
Bottou, Leon. 2011. β€œFrom Machine Learning to Machine Reasoning.” arXiv:1102.1808 [Cs], February.
Cancho, Ramon Ferrer i, and Ricard V. SolΓ©. 2003. β€œLeast Effort and the Origins of Scaling in Human Language.” Proceedings of the National Academy of Sciences 100 (3): 788–91.
Christiansen, Morten H, and Nick Chater. 2008. β€œLanguage as Shaped by the Brain.” Behavioral and Brain Sciences 31: 489–509.
Elman, Jeffrey L. 1991. β€œDistributed Representations, Simple Recurrent Networks, and Grammatical Structure.” Machine Learning 7: 195–225.
β€”β€”β€”. 1993. β€œLearning and Development in Neural Networks: The Importance of Starting Small.” Cognition 48: 71–99.
β€”β€”β€”. 1995. β€œLanguage as a Dynamical System,” 195.
Elman, Jeffrey L, Elizabeth A Bates, Mark H Johnson, Annette Karmiloff-Smith, Domenico Parisi, and Kim Plunkett. 1997. Rethinking Innateness: A Connectionist Perspective on Development (Neural Networks and Connectionist Modeling). The MIT Press.
Gold, E Mark. 1967. β€œLanguage Identification in the Limit.” Information and Control 10 (5): 447–74.
Greibach, Sheila A. 1966. β€œThe Unsolvability of the Recognition of Linear Context-Free Languages.” J. ACM 13 (4): 582–87.
β€”β€”β€”. 1969. β€œAn Infinite Hierarchy of Context-Free Languages.” J. ACM 16 (1): 91–106.
Hauser, Marc, and Jeffrey Watumull. 2016. β€œThe Universal Generative Faculty: The Source of Our Expressive Power in Language, Mathematics, Morality, and Music.” Journal of Neurolinguistics 43 (November): 78–94.
Hopcroft, John E., and Jeffrey D. Ullman. 1979. Introduction to Automata Theory, Languages and Computation. 1st ed. Addison-Wesley Publishing Company.
Jin, Dezhe Z. 2009. β€œGenerating Variable Birdsong Syllable Sequences with Branching Chain Networks in Avian Premotor Nucleus HVC.” Physical Review E 80 (5): 051902.
Jin, Dezhe Z, and Alexay A Kozhevnikov. 2011. β€œA Compact Statistical Model of the Song Syntax in Bengalese Finch.” PLoS Comput Biol 7 (3): –1001108.
John W Backus. 1959. β€œThe Syntax and Semantics of the Proposed International Algebraic Language of the Zurich ACM-GAMM Conference.” In Proceedings of the International Conference on Information Processing. ZΓΌrich: UNESCO.
Kirby, Simon. 1998. β€œLearning, Bottlenecks and the Evolution of Recursive Syntax.” In.
β€”β€”β€”. 2003. Language Evolution. Oxford University Press, USA.
Koshiba, Takeshi, Erkki MΓ€kinen, and Yuji Takada. 1997. β€œInferring Pure Context-Free Languages from Positive Data.” ACTA CYBERNETICA 14: 469–77.
Manning, Christopher D. 2002. β€œProbabilistic Syntax.” In Probabilistic Linguistics, 289–341. Cambridge, MA: MIT Press.
Mcclelland, James L, Matthew M Botvinick, David C Noelle, David C Plaut, Timothy T Rogers, Mark S Seidenberg, and Linda B Smith. 2010. β€œLetting Structure Emerge: Connectionist and Dynamical Systems Approaches to Cognition.” Trends in Cognitive Sciences 14 (8): 348–56.
Petersson, Karl-Magnus, Vasiliki Folia, and Peter Hagoort. 2012. β€œWhat Artificial Grammar Learning Reveals about the Neurobiology of Syntax.” Brain and Language, The Neurobiology of Syntax, 120 (2): 83–95.
Pullum, Geoffrey K, and Gerald Gazdar. 1982. β€œNatural Languages and Context-Free Languages.” Linguistics and Philosophy 4 (4): 471–504.
Shieber, Stuart M. 1987. β€œEvidence Against the Context-Freeness of Natural Language.” In The Formal Complexity of Natural Language, edited by Walter J. Savitch, Emmon Bach, William Marsh, and Gila Safran-Naveh, 320–34. Studies in Linguistics and Philosophy 33. Springer Netherlands.
Smith, Kenny, and Simon Kirby. 2008. β€œCultural Evolution: Implications for Understanding the Human Language Faculty and Its Evolution.” Philosophical Transactions of the Royal Society B: Biological Sciences 363: 3591–3603.
Wolff, J Gerard. 2000. β€œSyntax, Parsing and Production of Natural Language in a Framework of Information Compression by Multiple Alignment, Unification and Search.” Journal of Universal Computer Science 6 (8): 781–829.

No comments yet. Why not leave one?

GitHub-flavored Markdown & a sane subset of HTML is supported.