Syntax

Formal language theory

January 18, 2015 — June 22, 2016

compsci
language
neuron
stringology

What’s so special about speech anyway?

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

For now, see someone else writing about Chomsky Hierarchy.

Figure 1

Image from Hauser and Watumull (2016).

1 References

Autebert, Berstel, and Boasson. 1997. “Context-Free Languages and Pushdown Automata.” In Handbook of Formal Languages, Vol. 1.
Berstel, and Boasson. 1990. “Transductions and Context-Free Languages.” In Handbook of Theoretical Computer Science, Vol. A: Algorithms and Complexity.
Berwick, Okanoya, Beckers, et al. 2011. “Songs to Syntax: The Linguistics of Birdsong.” Trends in Cognitive Sciences.
Bolhuis, Tattersall, Chomsky, et al. 2014. “How Could Language Have Evolved?” PLoS Biol.
Bottou. 2011. “From Machine Learning to Machine Reasoning.” arXiv:1102.1808 [Cs].
Cancho, and Solé. 2003. “Least Effort and the Origins of Scaling in Human Language.” Proceedings of the National Academy of Sciences.
Christiansen, and Chater. 2008. “Language as Shaped by the Brain.” Behavioral and Brain Sciences.
Elman. 1991. “Distributed Representations, Simple Recurrent Networks, and Grammatical Structure.” Machine Learning.
———. 1993. “Learning and Development in Neural Networks: The Importance of Starting Small.” Cognition.
———. 1995. “Language as a Dynamical System.”
Elman, Bates, Johnson, et al. 1997. Rethinking Innateness: A Connectionist Perspective on Development (Neural Networks and Connectionist Modeling).
Gold. 1967. “Language Identification in the Limit.” Information and Control.
Greibach. 1966. “The Unsolvability of the Recognition of Linear Context-Free Languages.” J. ACM.
———. 1969. “An Infinite Hierarchy of Context-Free Languages.” J. ACM.
Hauser, and Watumull. 2016. “The Universal Generative Faculty: The Source of Our Expressive Power in Language, Mathematics, Morality, and Music.” Journal of Neurolinguistics.
Hopcroft, and Ullman. 1979. Introduction to Automata Theory, Languages and Computation.
Jin. 2009. “Generating Variable Birdsong Syllable Sequences with Branching Chain Networks in Avian Premotor Nucleus HVC.” Physical Review E.
Jin, and Kozhevnikov. 2011. “A Compact Statistical Model of the Song Syntax in Bengalese Finch.” PLoS Comput Biol.
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.
Kirby. 1998. “Learning, Bottlenecks and the Evolution of Recursive Syntax.” In.
———. 2003. Language Evolution.
Kleinberg, and Mullainathan. 2024. “Language Generation in the Limit.”
Koshiba, Mäkinen, and Takada. 1997. “Inferring Pure Context-Free Languages from Positive Data.” ACTA CYBERNETICA.
Manning. 2002. “Probabilistic Syntax.” In Probabilistic Linguistics.
Mcclelland, Botvinick, Noelle, et al. 2010. “Letting Structure Emerge: Connectionist and Dynamical Systems Approaches to Cognition.” Trends in Cognitive Sciences.
Petersson, Folia, and Hagoort. 2012. “What Artificial Grammar Learning Reveals about the Neurobiology of Syntax.” Brain and Language, The Neurobiology of Syntax,.
Pullum, and Gazdar. 1982. “Natural Languages and Context-Free Languages.” Linguistics and Philosophy.
Shieber. 1987. “Evidence Against the Context-Freeness of Natural Language.” In The Formal Complexity of Natural Language. Studies in Linguistics and Philosophy 33.
Smith, and Kirby. 2008. “Cultural Evolution: Implications for Understanding the Human Language Faculty and Its Evolution.” Philosophical Transactions of the Royal Society B: Biological Sciences.
Wolff. 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.