Statistically-based parsers for large corpora, in particular the Penn Tree Bank (PTB), typically have not used all the linguistic information encoded in the annotated trees on which they are trained. In particular, they have not in general used information that records the effects of derivations, such as empty categories and the representation of displaced phrases, as is the case with passive, topicalization, and wh-constructions. Here we explore ways to use this information to “unwind” derivations, yielding a regularized underlying syntactic structure that can be used as an additional source of information for more accurate parsing. In effect, we make use of two joint sets of tree structures for parsing: the surface structure and its corresponding underlying structure where arguments have been restored to their canonical positions. We present a pilot experiment on passives in the PTB indicating that through the use of these two syntactic representations we can improve overall parsing performance by exploiting transformational regularities, in this way paring down the search space of possible syntactic analyses.

This paper shows how to formally characterize language learning in a finite parameter space as a Markov structure. Important new language learning results follow directly: explicitly calculated sample complexity learning times under different input distribution assumptions (inclding CHILDES database language input) and learning regimes. We also briefly describe a new way to formally model (rapid) diachronic syntax change.

Conjunctions are particularly difficult to parse in traditional, phrase-based grammars. This paper shows how a different representation, not based on tree structures, markedly improves the parsing problem for conjunctions. It modifies the union of phrase marker model proposed by Goodall [1984], where conjunction is considered as the linearization of a three-dimensional union of a non-tree based phrase marker representation. A PROLOG grammar for conjunctions using this new approach is given. It is far simpler and more transparent than a recent phrase-based extraposition parser conjunctions by Dahl and McCord [1984]. Unlike the Dahl and McCord or ATN SYSCONJ approach, no special trail machinery is needed for conjunction, beyond that required for analyzing simple sentences. While of comparable efficiency, the new approach unifies under a single analysis a host of related constructions: respectively sentences, right node raising, or gapping. Another advantage is that it is also completely reversible (without cuts), and therefore can be used to generate sentences.

In this paper we apply some recent work of Angluin (1982) to the induction of the English auxiliary verb system. In general, the induction of finite automata is computationally intractable. However, Angluin shows that restricted finite automata, the k-reversible automata, can be learned by efficient (polynomial time) algoriths. can be learned by efficient (polynomial time) algorithms. We present an explicit computer model demonstrating that the English auxiliary verb system can in fact be learned as a l-reversible automaton, and hence in a computationally feasible amount of time. The entire system can be acquired by looking at only half the possible auxiliary verb sequences, and the pattern of generalization seems compatible with what is known about human acquisition of auxiliaries. We conclude that certain linguistic subsystems may well be learnable by inductive inference methods of this kind, and suggest an extension to context-free languages.

Natural languages are often assumed to be constrained so that they are either easily learnable or parsable, but few studies have investigated the connection between these two "functional" demands. Without a formal model of parsability or learnability, it is difficult to determine which is more "dominant" in fixing the properties of natural languages. In this paper we show that if we adopt one precise model of "easy" parsability, namely, that of bounded context parsability, and a precise model of "easy" learnability, namely, that of degree 2 learnability, then we can show that certain families of grammars that meet the bounded context parsability condition will also be degree 2 learnable. Some implications of this result for learning in other subsystems of linguistic knowledge are suggested.1

A central goal of linguistic theory is to explain why natural languages are the way they are. It has often been supposed that computational considerations ought to play a role in this characterization, but rigorous arguments along these lines have been difficult to come by. In this paper we show how a key "axiom" of certain theories of grammar, Subjacency, can be explained by appealing to general restrictions on on-line parsing plus natural constraints on the rule-writing vocabulary of grammars. The explanation avoids the problems with Marcus' [1980] attempt to account for the same constraint. The argument is robust with respect to machine implementation, and thus avoids the problems that often arise when making detailed claims about parsing efficiency. It has the added virtue of unifying in the functional domain of parsing certain grammatically disparate phenomena, as well as making a strong claim about the way in which the grammar is actually embedded into an on-line sentence processor.

Article Free Access Share on Computational complexity and lexical functional grammar Author: Robert C. Berwick MIT Artificial Intelligence Laboratory, Cambridge, MA MIT Artificial Intelligence Laboratory, Cambridge, MAView Profile Authors Info & Claims ACL '81: Proceedings of the 19th annual meeting on Association for Computational LinguisticsJune 1981Pages 7–12https://doi.org/10.3115/981923.981926Published:29 June 1981Publication History 2citation201DownloadsMetricsTotal Citations2Total Downloads201Last 12 Months13Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on Computational analogues of constraints on grammars: a model of syntactic acquisition Author: Robert Cregar Berwick MIT Artificial Intelligence Laboratory, Cambridge, MA MIT Artificial Intelligence Laboratory, Cambridge, MAView Profile Authors Info & Claims ACL '80: Proceedings of the 18th annual meeting on Association for Computational LinguisticsJune 1980 Pages 49–53https://doi.org/10.3115/981436.981453Published:19 June 1980Publication History 3citation165DownloadsMetricsTotal Citations3Total Downloads165Last 12 Months7Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF