Search

We present a novel approach to computing the context-sensitive flow of values through procedures and data structures. Our approach combines and extends techniques from two seemingly disparate areas: polymorphic subtyping and interprocedural dataflow analysis based on context-free language reachability. The resulting technique offers several advantages over previous approaches: it works directly on higher-order programs; provides demand-driven interprocedural queries; and improves the asymptotic complexity of a known algorithm based on polymorphic subtyping fromO(n8) toO(n3) for computing all queries. For intra-procedural flow restricted to equivalence classes, our algorithm yields linear inter-procedural flow queries.

The outcome of scientific research depends on how a phenomenon is viewed and how the questions are phrased. This applies also to the nativist view of language acquisition. As a complement to MacWhinney’s discussion of nativism from the viewpoint of cognitive psychology, I would like to devote this commentary to the question of the title from the viewpoint of computational linguistics. Formally, the nativist approach has been based on a distinction between finite and infinite sets. Chomsky defines a language as an infinite set of strings (sequence of word forms) and a grammar as a filter which picks the grammatically correct strings from the free monoid over the finite lexicon of the language. 1 Language acquisition is described in terms of a language acquisition device (LAD) which has the task of selecting from the infinite set of possible grammars the one which is correct for the language in question. The ‘ logical problem of language acquisition ’ is how the LAD can select a grammar which is correct for an infinite language, even though the data presented to the LAD (observed sentences) are necessarily finite. This problem is only made worse by Chomsky’s alleged degeneracy of input and poverty of negative evidence, focused on by MacWhinney. Given that humans can obviously learn language anyway, something in addition to a finite set of data is required. According to Chomsky, it is some innate universal grammar, common to all languages. Differences between languages are attributed to different parameter settings of the universal grammar. As empirical proof for the existence of a universal grammar we are offered language structures claimed to be learned ERROR-FREE. They are explained

Many of the processing steps in natural language engineering can be performed using finite state transducers. An optimal way to create such transducers is to compile them from regular expressions. This paper is an introduction to the regular expression calculus, extended with certain operators that have proved very useful in natural language applications ranging from tokenization to light parsing. The examples in the paper illustrate in concrete detail some of these applications.

Are rules processes or similarity processes the default for acquisition of grammatical knowledge during natural second language acquisition? Whereas Pothos argues similarity processes are the default in the many areas he reviews, including artificial grammar learning and first language development, I suggest, citing evidence, that in second language acquisition of grammatical morphology “rules processes” may be the default.

This essay by Truscott and Sharwood-Smith is a valiant attempt with a laudable goal. It seeks to show how different perspectives and disciplines can capture what is happening in acquisition and notably in L2 acquisition. Nonetheless, I think that the results are much closer to an elaborated grammatical theory than an elaborated processing theory (thus it seems less important to me than to the authors to choose one label over the other). Their essential, sensible idea is that where different grammars provide independent analyses of constructions, both are computed (even where the lexical items belong to only one grammar). Therefore conflict is experienced which produces computational demands. However this is pure grammar – just a more sophisticated situation where, as I like to argue, the L2 person has Multiple Grammars (Roeper, 1999), creating more computational work as well. In this respect, the situation is no different from L1 acquisition, where the course of acquisition involves generation and maintenance of multiple grammars, some of which are shed and some retained in the Final State.

i) We show for each context-free language L that by considering each word of L as a structure in a natural way, one turns L into a finite union of classes which satisfy a finitary analog of the characteristic properties of complete universal first order classes of structures equipped with elementary embeddings. We show this to hold for a much larger class of languages which we call free local languages, ii) We define local languages, a class of languages between free local and context-sensitive languages. Each local language L has a natural extension L∞ to infinite words, and we prove a series of “pumping lemmas”, analogs for each local language L of the “uvxyz theorem” of context free languages: they relate the existence of large words in L or L∞ to the existence of infinite “progressions” of words included in L, and they imply the decidability of various questions about L or L∞. iii) We show that the pumping lemmas of ii) are independent from strong axioms, ranging from Peano arithmetic to ZF + Mahlo cardinals.We hope that these results are useful for a model-theoretic approach to the theory of formal languages.