Inferring the formal language which can describe a set of expressions. In
human natural language, this means discovering the syntactic rules of a given
language. The problems are much broader and more interesting than this. I’ve
mentioned some of the applications at Design grammars. Essentially, if
it moves, someone has modelled it as a grammar. (Which is odd, as grammars are
not so great at describing dynamic hierarchies, as a rule, but that’s another
story.)
There is a lot of, a lot, of work in finding Markov processes that can produce
certain structures. I’m interested, for various reasons, in the things a rung
or two up the Chomsky hierarchy - Context free design grammars, maybe even
context sensitive ones.
Peter Norvig on Chomsky and statistical versus explanatory models of natural language syntax
Cosma Shalizi’s inevitable mention in 3, 2, 1... go
Alan Dorin, Jon McCormack. 2003. Self-assembling dynamical hierarchies. Artificial Life Eight.
Andreas Blume. 2004. A Learning-Efficiency Explanation of Structure in Language. Theory and Decision. _. (Online)
Aniruddh D Patel. 2003. Language, music, syntax and the brain. Nat Neurosci. _. (Online)
Bill Keller, Rüdi Lutz. 2000. Evolving Stochastic Context-Free Grammars from Examples Using a Minimum Description Length Principle. Paper presented at the Workshop on Automata Induction Grammatical Inference and Language Acquisition, ICML-97. (Online)
Colin De la Higuera. 2010. Grammatical inference : learning automata and grammars.
Dan Klein, Christopher D Manning. 2005. Natural language grammar induction with a generative constituent-context model. Grammatical Inference. _. (Online)
Denis, Lemay, Terlutte. 2004. Learning regular languages using RFSAs. Algorithmic Learning Theory. _. (Online)
Dupont, Denis, Esposito. 2005. Links between probabilistic automata and hidden Markov models: probability distributions, learning models and induction algorithms. Pattern Recognition. _. (Online)
E Csuhaj-Varjú, Kelemen, A Kelemenová, G Păun. 1997. Eco-grammar systems: a grammatical framework for studying lifelike interactions.. Artif Life. (Online)
Eugene Charniak. 1996. Statistical Language Learning. (Online)
Francisco Casacuberta, Enrique Vidal, David Pico. 2005. Inference of finite-state transducers from regular languages. Grammatical Inference. _. (Online)
Fred Lerdahl, Ray Jackendoff. 1996. A Generative Theory of Tonal Music. (Online)
Ian Dempsey, Michael O’Neill, Anthony Brabazon. 2009. Foundations in Grammatical Evolution for Dynamic Environments (Studies in Computational Intelligence). (Online)
James Hurford. 2000. The emergence of syntax. The Evolutionary Emergence of Language: Social Function and the Origins of Linguistic Form. (Online)
James Jay Horning. 1969. A study of grammatical inference.
Jeffrey G Long, Dorothy E Denning. 1995. Ultra-structure: a design theory for complex systems and processes. Commun. ACM. _. (Online)
Jeffrey L Elman. 1991. Distributed representations, simple recurrent networks, and grammatical structure. Machine Learning. _. (Online)
Jerry O Talton, Yu Lou, Steve Lesser, Jared Duke, Radom’ir Mvech, Vladlen Koltun. 2011. Metropolis procedural modeling. ACM Trans. Graph.. _. (Online)
John Batali. 1998. The negotiation and acquisition of recursive grammars as a result of competition among exemplars. Beyond Grammar: an experience-based theory of language. (Online)
Jon McCormack. Generative modelling with timed L-systems. Design Computing and Cognition.
Jon McCormack. 2004. Aesthetic Evolution of L-Systems Revisited. Applications of Evolutionary Computing. _. (Online)
K Johnson. 2004. Gold’s theorem and cognitive science. Philosophy of Science.
L Araujo. 2000. Evolutionary parsing for a probabilistic context free grammar. Proc. of the Int. Conf. on on Rough Sets and Current Trends in Computing (RSCTC-2000), Lecture Notes in Computer Science 2005. _. (Online)
M F Barnsley. Fractal image compression. Notices of the AMS.
Myung J Choi, Vincent Y Tan, Animashree Anandkumar, Alan S Willsky. 2010. Learning Latent Tree Graphical Models. (Online)
Nick Haslam. 1997. Four grammars for Primate Social Relations. Groups as the mind’s natural environment. (Online)
Ning Gu. 2006. Dynamic Designs of Virtual Worlds Using Generative Design Agents. (Online)
Peter F Dominey. 2005. From Sensorimotor Sequence to Grammatical Construction: Evidence from Simulation and Neurophysiology. Adaptive Behavior. _. (Online)
Przemyslaw Prusinkiewicz, Aristid Lindenmayer. 1991. The Algorithmic Beauty of Plants (The Virtual Laboratory). (Online)
Remo Badii, Antonio Politi. 1999. Complexity: Hierarchical Structures and Scaling in Physics (Cambridge Nonlinear Science Series). (Online)
Robert I McKay, Nguyen X Hoai, Peter A Whigham, Yin Shan, Michael O’Neill. 2010. Grammar-based Genetic Programming: a survey. Genetic Programming and Evolvable Machines. _. (Online)
Rudi Lutz, Bill Keller. 2005. Evolutionary induction of stochastic context free grammars. Pattern Recognition. _. (Online)
RW Byrne. 2003. Imitation as behaviour parsing.. Philos Trans R Soc Lond B Biol Sci. _. (Online)
Simon Mcgregor, Chrisantha Fernando. 2005. Levels of Description: A Novel Approach to Dynamical Hierarchies. Artificial Life. _. (Online)
Steven Pinker, Paul Bloom. 1990. Natural language and natural selection. Behavioral and Brain Sciences. (Online)
Suppes. 2002. Representation and invariance of scientific structures. (Online)
Tony C Smith, Ian H Witten. 1995. A Genetic Algorithm for the Induction of Natural Language Grammars. Proc IJCAI-95 Workshop on New Approaches to Learning for Natural Language Processing. (Online)
Wojciech Palubicki, Kipp Horel, Stephen Longay, Adam Runions, Brendan Lane. Self-organizing tree models for image synthesis. SIGGRAPH.
Wolff. 1998. Parsing as information compression by multiple alignment. (Online)