[41] Gregory M. Kobele. Actual Language Use and Competence Grammars. Theoretical Linguistics, 42(3-4):277--290, 2016. [ bib | DOI | pdf ]
This is a commentary on an article by Ruth Kempson et al. motivating dynamic syntax. I clarify their position against competence/performance and other distinctions, and argue that 1. incremental interpretation comes `for free' with compositional semantic interpretation, and 2. traditional `competence' grammars can account for split utterances in dialogue in exactly the way proposed by Kempson et al.

[40] Gregory M. Kobele and Jason Merchant. The Dynamics of Elllipsis. Theoretical Linguistics, 42(3-4):291--296, 2016. [ bib | DOI | pdf ]
This is a commentary on an article by Ruth Kempson et al. motivating dynamic syntax. We claim that the Dynamic Syntax approach to ellipsis is an instance of one which is common to many frameworks. We describe Kobele's (2015) account (which is in the same vein), and suggest that mismatches in ellipsis will prove difficult for the DS variant.

[39] Alexander Clark, Makoto Kanazawa, Gregory M. Kobele, and Ryu Yoshinaka. Distributional Learning of Some Nonlinear Tree Grammars. Fundamenta Informaticae, 146(4):339--377, 2016. [ bib | DOI | pdf ]
A key component of Clark and Yoshinaka's distributional learning algorithms is the extraction of substructures and contexts contained in the input data. This problem often becomes intractable with nonlinear grammar formalisms due to the fact that more than polynomially many substructures and/or contexts may be contained in each object. Previous works on distributional learning of nonlinear grammars avoided this difficulty by restricting the substructures or contexts that are made available to the learner. In this paper, we identify two classes of nonlinear tree grammars for which the extraction of substructures and contexts can be performed in polynomial time, and which, consequently, admit successful distributional learning in its unmodified, original form.

[38] Gregory M. Kobele. LF-copying without LF. Lingua, 166, part B:236--259, 2015. [ bib | DOI | pdf ]
A copying approach to ellipsis is presented, whereby the locus of copying is not a level of derived syntactic structure (LF), but rather the derivation itself. The ban on preposition stranding in sprouting follows without further stipulation, and other, seemingly structure sensitive, empirical generalizations about elliptical constructions, including the preposition stranding generalization, follow naturally as well. Destructive operations which `repair' non-identical antecedents are recast in terms of exact identity of derivations with parameters. In the context of a compositional semantic interpretation scheme, the derivational copying approach to ellipsis presented here is revealed to be a particular instance of a proform theory, thus showing that the distinctions between, and arguments about, syntactic and semantic theories of ellipsis need to be revisited.

[37] Gregory M. Kobele and Sylvain Salvati. The IO and OI hierarchies, revisited. Information and Computation, 243:205--221, 2015. [ bib | DOI | pdf ]
We study languages of λ-terms generated by IO and OI unsafe grammars. These languages can be used to model meaning representations in the formal semantics of natural languages following the tradition of Montague. Using techniques pertaining to the denotational semantics of the simply typed λ-calculus, we show that the emptiness and membership problems for both types of grammars are decidable. In the course of the proof of the decidability results for OI, we identify a decidable variant of the λ-definability problem, and prove a stronger form of Statman's finite completeness Theorem.

[36] John Case, Jeffrey Heinz, and Gregory M. Kobele. Interpreted Learning: A framework for investigating the contribution of various information sources to the learning problem. In Carson T. Schütze and Linnaea Stockall, editors, Connectedness: Papers by and for Sarah VanWagenen, volume 18 of UCLA Working Papers in Linguistics, pages 90--101. UCLA, 2014. [ bib | pdf | .html ]
Natural language utterances presents learners with more information about the underlying grammar than is typically encoded in the orthographic string. While multiple information sources such as prosody, and semantics can be encoded as a single object, allowing the results of typical learning frameworks to apply, this coding obscures the question of exactly how the learner can draw inferences about a single object from information made available by these multiple different perspectives. Here we tease apart the contribution of different information sources to the learning problem by generalizing Gold's learning paradigm. The main result is a proof that multiple sources of information can interact synergistically to facilitate learning of the target underlying grammar.

[35] Gregory M. Kobele. Meeting the Boojum. Theoretical Linguistics, 40(1-2):165--173, 2014. [ bib | DOI | pdf ]
This is a commentary on an article by Müller and Wechsler comparing lexical and phrasal approaches to argument structure. I claim that the basic distinction they are making between lexical and phrasal approaches is not well defined, that their arguments are circular, and that their complexity metric is unmotivated.

[34] Makoto Kanazawa, Gregory M. Kobele, Jens Michaelis, Sylvain Salvati, and Ryo Yoshinaka. The failure of the strong pumping lemma for multiple context-free languages. Theory of Computing Systems, 55(1):250--278, 2014. [ bib | DOI | pdf ]
Seki et al. (“On multiple context-free grammars”, Theoretical Computer Science 88 (1991)) showed that every m-multiple context-free language L is weakly 2m-iterative. Whether every m-multiple context-free language L is 2m-iterative has been open. We show that there is a 3-multiple context-free language that is not k-iterative for any k.

[33] Gregory M. Kobele and Sylvain Salvati. The IO and OI Hierarchies Revisited. In Fedor V. Fomin, Rusins Freivalds, Marta Kwiatkowska, and David Peleg, editors, Automata, Languages, and Programming, volume 7966 of Lecture Notes in Computer Science, pages 336--348. Springer, Berlin, 2013. [ bib | DOI | pdf | http ]
We study languages of λ-terms generated by IO and OI unsafe grammars. These languages can be used to model meaning representations in the formal semantics of natural languages following the tradition of Montague. Using techniques pertaining to the denotational semantics of the simply typed λ-calculus, we show that the emptiness and membership problems for both types of grammars are decidable. In the course of the proof of the decidability results for OI, we identify a decidable variant of the λ-definability problem, and prove a stronger form of Statman's finite completeness Theorem.

[32] Gregory M. Kobele, Sabrina Gerth, and John T. Hale. Memory Resource Allocation in Top-Down Minimalist Parsing. In Glyn Morrill and Mark-Jan Nederhof, editors, FG 2012/2013, volume 8036 of Lecture Notes in Computer Science, pages 32--51. Springer, Heidelberg, 2013. [ bib | DOI | pdf ]
This paper provides a linking theory between the minimalist grammar formalism and off-line behavioural data. We examine the transient stack states of a top-down parser for Minimalist Grammars as it analyzes embedded sentences in English, Dutch and German. We find that the number of time steps that a derivation tree node persist on the parser's stack derives the observed contrasts in English center embedding, and the difference between German and Dutch embedding. This particular stack occupancy measure formalizes the leading idea of “memory burden” in a way that links predictive, incremental parsing to specific syntactic analyses.

[31] Gregory M. Kobele. Idioms and extended transducers. In Proceedings of the 11th International Workshop on Tree Adjoining Grammars and Related Formalisms (TAG+11), pages 153--161, Paris, France, September 2012. [ bib | pdf | html ]
There is a tension between the idea that idioms can be both listed in the lexicon, and the idea that they are themselves composed of the lexical items which seem to inhabit them in the standard way. In other words, in order to maintain the insight that idioms actually contain the words they look like they contain, we need to derive them syntactically from these words. However, the entity that should be assigned a special meaning is then a derivation, which is not the kind of object that can occur in a lexicon (which is, by definition, the atoms of which derivations are built), and thus not the kind of thing that we are able to assign meanings directly to. Here I show how to resolve this tension in an elegant way, one which bears striking similarities to those proposed by psychologists and psycholinguists working on idioms.

[30] Gregory M. Kobele and Jens Michaelis. On the Form-Meaning Relations Definable by CoTAGs. In Proceedings of the 11th International Workshop on Tree Adjoining Grammars and Related Formalisms (TAG+11), pages 207--213, Paris, France, September 2012. [ bib | pdf | html ]
Barker notes that from a purely syntactic perspective, in the context of simple (i.e. not multicomponent) TAGs, adding cosubstitution affects neither weak nor strong generative capacity (in the sense of derived string and tree languages). Clearly, however, something is different: after adding the operation of cosubstitution, derivational order matters in the sense that one derived syntactic representation can potentially be associated with more than one simultaneously derived semantic representation. As Barker points out, the introduction of the cosubstitution operator allows for a straightforward adaption of the notion of derivation tree such that two derivation trees can be different depending on when a cosubstitution step takes place. We demonstrate that the form-meaning mappings definable by coTAGs go beyond those of “simple” STAGs (Shieber, 1994; Shieber, 2006). In particular, the set of meanings, the second projection of the synchronously derived syntactic and semantic representations, can be -- up to a homomorphism abstracting away from instances of λ and variables -- the non-tree adjoining language MIX(k), for any k >=3.

[29] Gregory M. Kobele. Eliding the Derivation: A Minimalist Formalization of Ellipsis. In Stefan Müller, editor, Proceedings of the 19th International Conference on Head-Driven Phrase Structure Grammar, Chungnam National University Daejeon, pages 307--324, Stanford, 2012. CSLI Publications. [ bib | pdf | html ]
In this paper I use the formal framework of minimalist grammars to implement a version of the traditional approach to ellipsis as `deletion under syntactic (derivational) identity,' which, in conjunction with canonical analyses of voice phenomena, immediately allows for voice mismatches in verb phrase ellipsis, but not in sluicing. This approach to ellipsis is naturally implemented in a parser by means of threading a state encoding a set of possible antecedent derivation contexts through the derivation tree. Similarities between ellipsis and pronominal resolution are easily stated in these terms. In the context of this implementation, two approaches to ellipsis in the transformational community are naturally seen as equivalent descriptions at different levels: the LF-copying approach to ellipsis resolution is best seen as a description of the parser, whereas the phonological deletion approach a description of the underlying relation between form and meaning

[28] Gregory M. Kobele. Deriving Reconstruction Asymmetries. In Artemis Alexiadou, Tibor Kiss, and Gereon Müller, editors, Local Modeling of Non-Local Dependencies in Syntax, volume 547 of Linguistische Arbeiten, pages 477--500. de Gruyter, Berlin, 2012. [ bib | pdf | html ]
There appears to be a systematic difference in the reconstructability of noun phrases and predicates. In this paper I show that reconstructing the A/A-bar distinction in terms of slash-feature percolation and movement allows for a simple derivational formulation of the principles of binding and scope which derives a generalization very much along the lines of the one presented by Huang (1993).

[27] Gregory M. Kobele and Malte Zimmermann. Quantification in German. In Edward L. Keenan and Denis Paperno, editors, Handbook of Quantifiers in Natural Language, volume 90 of Studies in Linguistics and Philosophy, chapter 5, pages 227--283. Springer, Berlin, 2012. [ bib | DOI | pdf ]
This paper is a systematic survey of the linguistic expression of quantification in German.

[26] Gregory M. Kobele. Importing Montagovian Dynamics into Minimalism. In Denis Béchet and Alexandre Dikovsky, editors, Logical Aspects of Computational Linguistics, volume 7351 of Lecture Notes in Computer Science, pages 103--118, Berlin, 2012. Springer. [ bib | DOI | pdf ]
Minimalist analyses typically treat quantifier scope interactions as being due to movement, thereby bringing constraints thereupon into the purview of the grammar. Here we adapt De Groote's continuation-based presentation of dynamic semantics to minimalist grammars. This allows for a simple and simply typed compositional interpretation scheme for minimalism

[25] Gregory M. Kobele and Jens Michaelis. CoTAGs and ACGs. In Denis Béchet and Alexandre Dikovsky, editors, Logical Aspects of Computational Linguistics, volume 7351 of Lecture Notes in Computer Science, pages 119--134, Berlin, 2012. Springer. [ bib | DOI | pdf ]
Our main concern is to provide a complete picture of how coTAGs, as a particular variant within the general framework of tree adjoining grammars (TAGs), can be captured under the notion of abstract categorial grammars (ACGs). coTAGs have been introduced by Barker as an “alternative conceptualization” in order to cope with the tension between the TAG-mantra of the “locality of syntactic dependencies” and the seeming non-locality of quantifier scope. We show how our formalization of Barker's proposal leads to a class of higher order ACGs. By taking this particular perspective, Barker's proposal turns out as a straightforward extension of the proposal of Pogodalla, where the former in addition to “simple” inverse scope phenomena also captures inverse linking and non-inverse linking phenomena.

[24] Gregory M. Kobele. Ellipsis: Computation of. WIREs Cognitive Science, 3(3):411--418, 2012. [ bib | DOI | pdf ]
A computational account of ellipsis should specify not only how the meaning of an elliptical sentence is computed in context, but also a description of what is being computed. Many proposals can be divided into two groups, as per whether they compute the meaning of an elliptical sentence based on the semantic or the syntactic parts of its context. A unifying theme of these proposals is that they are all based on the idea that the meaning of an elliptical sentence is determinable based on a structured representation which is transformationally related to its surface syntactic structure.

[23] Gregory M. Kobele and Jens Michaelis. Disentangling Notions of Specifier Impenetrability: Late Adjunction, Islands, and Expressive Power. In Makoto Kanazawa, András Kornai, Marcus Kracht, and Hiroyuki Seki, editors, The Mathematics of Language, volume 6878 of Lecture Notes in Computer Science, pages 126--142. Springer, Berlin, 2011. [ bib | DOI | pdf ]
In this paper we investigate the weak generative capacity of minimalist grammars with late adjunction. We show that by viewing the Specifier Island Condition as the union of three separate constraints, we obtain a more nuanced perspective on previous results on constraint interaction in minimalist grammars, as well as the beginning of a map of the interaction between late adjunction and movement constraints. Our main result is that minimalist grammars with the SpIC on movement generated specifiers only and with the Shortest Move Constraint, in conjunction with late adjunction, can define languages whose intersection with an appropriate regular language is not semilinear.

[22] Christina S. Kim, Gregory M. Kobele, Jeffery T. Runner, and John T. Hale. The acceptability cline in VP ellipsis. Syntax, 14(4):318--354, 2011. [ bib | DOI | pdf ]
This paper lays the foundations for a processing model of relative acceptability levels in verb phrase ellipsis (VPE). In the proposed model, mismatching VPE examples are grammatical but less acceptable because they violate heuristic parsing strategies. This analysis is presented in a Minimalist Grammar formalism that is compatible with standard parsing techniques. The overall proposal integrates computational assumptions about parsing with a psycholinguistic linking hypothesis. These parts work together with the syntactic analysis to derive novel predictions that are confirmed in a controlled experiment.

[21] Gregory M. Kobele. Minimalist Tree Languages are Closed under Intersection with Recognizable Tree Languages. In Sylvain Pogodalla and Jean-Philippe Prost, editors, LACL 2011, volume 6736 of Lecture Notes in Artificial Intelligence, pages 129--144, Berlin, 2011. Springer. [ bib | DOI | pdf ]
Minimalist grammars are a mildly context-sensitive grammar framework within which analyses in mainstream chomskyian syntax can be faithfully represented. Here it is shown that both the derivation tree languages and derived tree languages of minimalist grammars are closed under intersection with regular tree languages. This allows us to conclude that taking into account the possibility of `semantic crashes' in the standard approach to interpreting minimalist structures does not alter the strong generative capacity of the formalism. In addition, the addition to minimalist grammars of complexity filters is easily shown using a similar proof method to not change the class of derived tree languages.

[20] Gregory M. Kobele. A Formal Foundation for A and A-bar Movement in the Minimalist Program. In Christian Ebert, Gerhard Jäger, and Jens Michaelis, editors, MOL 10/11, volume 6149 of Lecture Notes in Computer Science, pages 145--159. Springer, Berlin, 2010. [ bib | DOI | pdf ]
It seems a fact that movement dependencies come in two flavours: “A” and “A-bar”. Over the years, a number of apparently independent properties have been shown to cluster together around this distinction. However, the basic structural property relating these two kinds of movement, the ban on improper movement (`once you go bar, you never go back'), has never been given a satisfactory explanation. Here, I propose a timing-based account of the A/A-bar distinction, which derives the ban on improper movement, and allows for a simple and elegant account of some of their differences. In this account, “A” dependencies are those which are entered into before an expression is first merged into a structure, and “A-bar” dependencies are those an expression enters into after having been merged. The resulting system is mildly context-sensitive, providing therefore a restrictive account of possible human grammars, while remaining expressive enough to be able to describe the kinds of dependencies which are thought to be manifest.

[19] Gregory M. Kobele. Without Remnant Movement, MGs are Context-Free. In Christian Ebert, Gerhard Jäger, and Jens Michaelis, editors, MOL 10/11, volume 6149 of Lecture Notes in Computer Science, pages 160--173. Springer, Berlin, 2010. [ bib | DOI | pdf ]
Minimalist grammars offer a formal perspective on a popular linguistic theory, and are comparable in weak generative capacity to other mildly context sensitive formalism. Minimalist grammars allow for the straightforward definition of so-called remnant movement constructions, which have found use in many linguistic analyses. It has been conjectured that the ability to generate this kind of configuration is crucial to the super-context-free expressivity of minimalist grammars. This conjecture is here proven.

[18] Gregory M. Kobele. Inverse Linking via Function Composition. Natural Language Semantics, 18(2):183--196, 2010. [ bib | DOI | pdf ]
The phenomenon of Inverse Linking has proven challenging for theories of the syntax-semantics interface; a noun phrase within another behaves with respect to binding as though it were structurally independent. In this paper I show that, using an LF-movement style approach to the syntax-semantics interface, we can derive all and only the appropriate meanings for such constructions using no semantic operations other than function application and composition. The solution relies neither on a proliferation of lexical ambiguity nor on abandoning the idea that pronouns denote variables, but rather on a straightforward (and standard) reification of assignment functions, which allows us to define abstraction operators within our models.

[17] Jeffrey Heinz, Gregory M. Kobele, and Jason Riggle. Evaluating the Complexity of Optimality Theory. Linguistic Inquiry, 40(2):277--288, 2009. [ bib | DOI | pdf ]
Idsardi (2006) claims that Optimality Theory (OT; Prince and Smolensky 1993/2004) is “in general computationally intractable” on the basis of a proof adapted from Eisner (1997a). We take issue with this conclusion on two grounds. First, the intractability result holds only in cases where the constraint set is not fixed in advance (contra usual definitions of OT) and second, the result crucially depends on a particular representation of OT grammars. We show that there is an alternative representation of OT grammars that allows for efficient computation of optimal surface forms and provides deeper insight into the sources of complexity of Optimality Theory. We conclude that it is a mistake to reject Optimality Theory on the grounds that it is computationally intractable.

[16] Gregory M. Kobele. Syntactic Identity in Survive Minimalism: Ellipsis and the Derivational Identity Hypothesis. In Michael T. Putnam, editor, Towards a derivational syntax: Survive-minimalism. John Benjamins, Amsterdam, 2009. [ bib | pdf | html ]
Over the years, a number of counter-examples to the hypothesis that ellipsis resolution is mediated via syntactic identity have been identified. However, in the same time evidence which seems to require comparison of syntactic structures in ellipsis resolution has also been unearthed. On top of this empirical puzzle, survive minimalism places an additional theoretical constraint: syntactic structures, once assembled, are opaque to further search or manipulation. In this paper, I show that a simple perspective shift allows us both to view the purported counter-examples as providing glimpses into the nature of the operations which build syntactic structure, and to satisfy the theoretical constraints imposed by survive minimalism's derivational take on syntactic structure.

[15] Gregory M. Kobele. Across-the-Board Extraction in Minimalist Grammars. In Proceedings of the Ninth International Workshop on Tree Adjoining Grammar and Related Formalisms (TAG+9), pages 113--128, 2008. [ bib | pdf ]
Minimalist grammars cannot provide adequate descriptions of constructions in which a single filler saturates two mutually independent gaps, as is commonly analyzed to be the case in parasitic gap constructions and other across-the-board extraction phenomena. In this paper, I show how a simple addition to the minimalist grammar formalism allows for a unified treatment of control and parasitic gap phenomena, and can be restricted in such a way as to account for across-the-board exceptions to the coordinate structure constraint. In the context of standard constraints on movement, the weak generative capacity of the formalism remains unaffected.

[14] Gregory M. Kobele. Agreement Bottlenecks in Italian. In Claudia Casadio and Joachim Lambek, editors, Computational Algebraic Approaches to Natural Language, pages 191--212. Polimetrica, Milan, 2008. [ bib | pdf | html ]
This paper follows a progression of pregroup analyses of agreement in the Italian DP as they are successively modified so as to express more sophisticated relationships between overt expressions of agreement. The desire to state our intuitions about the data directly in the object language of the theory will be seen to put pressures on the underlying combinatory system that the types will be unable to accommodate. Allowing more expressive types (while holding constant the underlying calculus) will alleviate some of the pressure put on the combinatory system, and allow us to capture certain generalizations about relations between paradigms that are out of the reach of previous analyses. In particular, it will be shown that certain kinds of `meta-paradigmatic' phenomena [Bobaljik, 2002] are statable without additional stipulation in our setting.

[13] Gregory M. Kobele, Christian Retoré, and Sylvain Salvati. An automata theoretic approach to minimalism. In James Rogers and Stephan Kepser, editors, Proceedings of the Workshop Model-Theoretic Syntax at 10; ESSLLI '07, Dublin, 2007. [ bib | pdf | html ]
We show in this paper how, given a minimalist grammar G, to construct a simple, regular, characterization of its well formed derivations. We obtain both a bottom-up and a top-down characterization of the function from minimalist derivations to derived trees. The same construction extends to minimalist grammars with copying. In other words, the structure languages generated by minimalist grammars with (without) copying are contained in the output languages of (finite copying) tree homomorphisms. Compositionality is naturally formulated as a transduction mapping derivation trees to (terms denoting) semantic values. The compositional semantics for minimalist grammars introduced in Kobele (2006) is naturally expressed in terms of a transduction of the same type as that mapping derivations to derived trees. We present a general method of synchronizing (in the sense of Shieber (1994)) multiple transductions over the same derivation, showing as a result that the form-meaning relations definable by MGs interpreted as per Kobele (2006) can be described as bimorphisms of type B(M,M).

[12] Gregory Kobele and Harold Torrence. Intervention and focus in Asante Twi. In Ines Fiedler and Anne Schwarz, editors, Papers on Information Structure in African Languages, volume 46(12) of ZAS Papers in Linguistics, pages 161--184. ZAS, Berlin, 2006. [ bib | pdf | html ]
This paper concerns the distribution of wh-words in Asante Twi, which has both a focus fronting strategy and an in-situ strategy. We show that the focusing and the in-situ constructions are not simply equally available options. On the contrary, there are several cases where the focusing strategy must be used and the in-situ strategy is ungrammatical. We show that the cases in Asante Twi are “intervention effects”, which are attested in other languages, like German, Korean, and French. We identify a core set of intervening elements that all of these languages have and discuss their properties.

[11] Gregory M. Kobele and Marcus Kracht. Pregroup Grammars are Turing Complete. In Aviad Eilam, Tatjana Scheffler, and Joshua Tauberer, editors, Proceedings of the 29th Pennsylvania Linguistics Colloquium, volume 12 of University of Pennsylvania Working Papers in Linguistics, pages 189--198, 2006. [ bib | pdf | html ]
Pregroups were introduced in (Lambek, 1999), and provide a foundation for a particularly simple syntactic calculus. Buszkowski (2001) showed that free pregroup grammars generate exactly the ε-free context-free languages. Here we characterize the class of languages generable by all pregroups, which will be shown to be the entire class of recursively enumerable languages. To show this result, we rely on the well-known representation of recursively enumerable languages as the homomorphic image of the intersection of two context-free languages (Ginsburg et al., 1967). We define an operation of cross-product over grammars (so-called because of its behaviour on the types), and show that the cross-product of any two free-pregroup grammars generates exactly the intersection of their respective languages. The representation theorem applies once we show that allowing `empty categories' (i.e. lexical items without overt phonological content) allows us to mimic the effects of any string homomorphism.

[10] Gregory M. Kobele. Generating Copies: An investigation into structural identity in language and grammar. PhD thesis, University of California, Los Angeles, 2006. [ bib | pdf | html ]
[9] Gregory M. Kobele. Features moving madly: A formal perspective on feature percolation in the minimalist program. Research on Language and Computation, 3(4):391--410, 2005. [ bib | DOI | pdf ]
I show that adding a mechanism of feature percolation (via specifier head agreement) to Minimalist Grammars (MGs) [Stabler, 1997] takes them out of the class of context-sensitive grammar formalisms. The main theorem of the paper is that adding a mechanism of feature percolation to MGs allows them to implement infinite abaci [Lambek, 1961], which can simulate any Turing Machine computation. As a simple corollary, I show that, for any computable function f over natural numbers, MGs thus enhanced can generate the unary language corresponding to the range of f.

[8] Gregory M. Kobele and Jens Michaelis. Two Type 0-Variants of Minimalist Grammars. In Gerhard Jäger, Paola Monachesi, Gerald Penn, James Rogers, and Shuly Wintner, editors, Proceedings of the 10th conference on Formal Grammar and the 9th Meeting on Mathematics of Language, Stanford, 2009. CSLI Online Publications. [ bib | pdf | html ]
Minimalist grammars (Stabler 1997) capture some essential ideas about the basic operations of sentence construction in the Chomskyian syntactic tradition. Their affinity with the unformalized theories of working linguists makes it easier to implement and thereby to better understand the operations appealed to in neatly accounting for some of the regularities perceived in language. Here we characterize the expressive power of two, apparently quite different, variations on the basic minimalist grammar framework, gotten by either adding a mechanism of `feature percolation' (Kobele, 2005), or, instead of adding a central constraint on movement (the `specifier island condition', Stabler 1999), using it to replace another one (the `shortest move condition', Stabler 1997, 1999) (Gärtner and Michaelis, 2005). We demonstrate that both variants have equal, unbounded, computing power by showing how each can simulate straightforwardly a 2-counter automaton.

[7] Yoosook Lee, Travis C. Collier, Gregory M. Kobele, Edward P. Stabler, and Charles E. Taylor. Grammar Structure and the Dynamics of Language Evolution. In Mathieu S. Capcarrere, Alex A. Freitas, Peter J. Bentley, Colin G. Johnson, and Jon Timmis, editors, Advances in Artificial Life, volume 3630 of Lecture Notes in Computer Science, pages 624--633. Springer, Berlin, 2005. Proceedings of the 8th European Conference, ECAL 2005. [ bib | DOI | pdf ]
The complexity, variation, and change of languages make evident the importance of representation and learning in the acquisition and evolution of language. For example, analytic studies of simple language in unstructured populations have shown complex dynamics, depending on the fidelity of language transmission. In this study we extend these analysis of evolutionary dynamics to include grammars inspired by the principles and parameters paradigm. In particular, the space of languages is structured so that some pairs of languages are more similar than others, and mutations tend to change languages to nearby variants. We found that coherence emerges with lower learning fidelity than predicted by earlier work with an unstructured language space.

[6] Gregory M. Kobele, Jason Riggle, Richard Brooks, David Friedlander, Charles Taylor, and Edward Stabler. Induction of Prototypes in a Robotic Setting Using Local Search MDL. In Masanori Sugisaka and Hiroshi Tanaka, editors, Proceedings of the Ninth International Symposium on Artificial Life and Robotics, pages 482--485, 2004. [ bib | pdf ]
Categorizing objects sets the stage for more advanced interactions with the environment. Minimum Description Length learning provides a framework in which to investigate processes by which concept learning might take place. Importantly, the concepts so acquired can be viewed as having a prototype structure - the concepts may apply to one object better than to another. We ground our discussion in a real-world setting - objects to categorize are sensor readings of the behaviours of two mobile robots.

[5] Gregory M. Kobele, Jason Riggle, Travis C. Collier, Yoosook Lee, Ying Lin, Yuan Yao, Charles E. Taylor, and Edward P. Stabler. Grounding As Learning. In Simon Kirby, editor, Proceedings of the Workshop/Course on Language Evolution and Computation, ESSLLI `03, pages 87--94, Vienna, 2003. [ bib | pdf | html ]
Communication among agents requires (among many other things) that each agent be able to identify the semantic values of the generators of the language. This is the “grounding” problem: how do agents with different cognitive and perceptual experiences successfully converge on common (or at least sufficiently similar) meanings for the language? There are many linguistic studies of how human learners do this, and also studies of how this could be achieved in robotic contexts (e.g., (Steels, 1996; Kirby, 1999)). These studies provide insight, but few of them characterize the problem precisely. In what range of environments can which range of languages be properly grounded by distributed agents? This paper takes a first step toward bringing the tools of formal language theory to bear on this problem. In the first place, these tools easily reveal a number of grounding problems which are simply unsolvable with reasonable assumptions about the evidence available, and some problems that can be solved. In the second place, these tools provide a framework for exploring more sophisticated grounding strategies (Stabler et al., 2003). We explore here some preliminary ideas about how hypotheses about syntactic structure can interact with hypotheses about grounding in a fruitful way to provide a new perspective on the emergence of recursion in language. Simpler grounding methods look for some kind of correlation between the mere occurrence of particular basic generators and semantic elements, but richer hypotheses about relations among the generators themselves can provide valuable additional constraints on the problem.

[4] Gregory M. Kobele, Travis C. Collier, Charles E. Taylor, and Edward P. Stabler. Learning Mirror Theory. In Proceedings of the Sixth International Workshop on Tree Adjoining Grammars and Related Frameworks (TAG+6), Venice, 2002. [ bib | pdf ]
Here we investigate the learnability of classes of mirror-theoretic grammars from dependency structures, which show relations among the lexical items in a sentence, information which is, at least in many cases, plausibly available to the language learner (surface order, morphological decomposition and affixation and selection relations). We define conditions under which this is possible. Adapting a technique familiar from (Kanazawa, 1998) and others, we show that if the lexical ambiguity in target grammars is restricted, this can provide a basis for generalization from the finite sample. Our results show that the class of mirror theoretic grammars in which every lexical item has a unique phonetic string (the 1-rigid grammars) is identifiable in the limit from any text of dependency structures.

[3] Edward P. Stabler, Travis C. Collier, Gregory M. Kobele, Yoosook Lee, Ying Lin, Jason Riggle, Yuan Yao, and Charles E. Taylor. The Learning and Emergence of Mildly Context Sensitive Languages. In Wolfgang Banzhaf, Thomas Christaller, Peter Dittrich, Jan T. Kim, and Jens Ziegler, editors, Advances in Artificial Life, volume 2801 of Lecture Notes in Computer Science, pages 525--534. Springer, Berlin, 2003. [ bib | DOI | pdf ]
This paper describes a framework for studies of the adaptive acquisition and evolution of language, with the following components: language learning begins by associating words with cognitively salient representations (“grounding”); the sentences of each language are determined by properties of lexical items, and so only these need to be transmitted by learning; the learnable languages allow multiple agreements, multiple crossing agreements, and reduplication, as mildly context sensitive and human languages do; infinitely many different languages are learnable; many of the learnable languages include infinitely many sentences; in each language, inferential processes can be defined over succinct representations of the derivations themselves; the languages can be extended by innovative responses to communicative demands. Preliminary analytic results and a robotic implementation are described.

[2] Gregory M. Kobele. Formalizing Mirror Theory. Grammars, 5(3):177--221, 2002. [ bib | DOI | pdf ]
Mirror theory is a theory of (morpho-) syntax introduced in (Brody, 1997). Here I present a formalization of the theory, and study some of its language theoretic properties.

[1] Kyubum Wee, Travis C. Collier, Gregory M. Kobele, Edward P. Stabler, and Charles E. Taylor. Natural language interface to an intrusion detection system. In Proceedings, International Conference on Control, Automation and Systems. ICCAS, 2001. [ bib | pdf ]
Computer security is a very important issue these days. Computer viruses, worms, Trojan horses, and cracking are prevalent and causing serious damages. There are also many ways developed to defend against such attacks including cryptography and firewalls. However, it is not possible to guarantee complete security of computer systems or networks. Recently much attention has been directed to ways to detect intrusions and recover from damages. Although there have been a lot of research efforts to develop efficient intrusion detection systems, little has been done to facilitate the interaction between intrusion detection systems and users. Reports and presentations of current states of the computers or networks to the user in a format that is easy to understand as well as specification of security policies from the user are important aspects of intrusion detection systems. We present our first steps to develop natural language interface between a user and an intrusion detection system using minimalist transformational grammar and Prolog. Our system takes a pseudo-English query from the user, parses it using CYK -like algorithm, converts it into a formula in Horn logic, feeds it to Prolog, and then gets the answer back in a simple format.

This file was generated by bibtex2html 1.98.