We introduce and study a natural extension of Marcus external contextual grammars. This mathematically simple mechanism which generates a proper subclass of simple matrix languages, known to be mildly context-sensitive ones, is still mildly context-sensitive. Furthermore, we get an infinite hierarchy of mildly context-sensitive families of languages. Then we attempt to fill a gap regarding the linguistic relevance of these mechanisms which consists in defining a tree structure on the strings generated by many-dimensional external contextual grammars, and investigate some related (...) issues. Several open problems are finally discussed. (shrink)

In recent years, dependency grammars have established themselves as valuable tools in theoretical and computational linguistics. To many linguists, dependency grammars and the more standard constituency-based formalisms are notational variants. We argue that, beyond considerations of formal equivalence, cognition may also serve as a background for a genuine comparison between these different views of syntax. In this paper, we review and evaluate some of the most common arguments and evidence employed to advocate for the cognitive or neural reality of dependency (...) grammars in linguistics, psycholinguistics, or neurolinguistics. We then raise the possibility that the abilities to represent and track, alternatively or in parallel, constituency and dependency structures co-exist in human cognition and are constitutive of syntactic competence. (shrink)

We examine an argument for the non-context-freeness of English that has received virtually no discussion in the literature. It is based on adjuncts of the form 'X or no X', where X is a nominal. The construction has been held to exemplify unbounded syntactic reduplication. We argue that although the argument can be made in a mathematically valid form, its empirical basis is not secure. First, the claimed unbounded syntactic identity between nominals does not always hold in attested cases, and (...) second, an understanding of the semantics of the construction removes the necessity of making reference to any syntactic reduplication. (shrink)

Is formal simplicity a guide to learning in humans, as simplicity is said to be a guide to the acceptability of theories in science? Does simplicity determine the difficulty of various learning tasks? I argue that, similarly to how scientists sometimes preferred complex theories when this facilitated calculations, results from perception, learning and reasoning suggest that formal complexity is generally unrelated to what is easy to learn and process by humans, and depends on assumptions about available representational and processing primitives. (...) “Simpler” hypotheses are preferred only when they are also easier to process. Historically, “simpler”, easier‐to‐process, scientific theories might also be preferred if they are transmitted preferentially. Empirically viable complexity measures should build on the representational and processing primitives of actual learners, even if explanations of their behaviour become formally more complex. (shrink)

Back in the 1980’s, the class of mildly context-sensitive formalisms was introduced so as to capture the syntax of natural languages. While the languages generated by such formalisms are constrained by the constant-growth property, the most well-known and used ones—like tree-adjoining grammars or multiple context-free grammars—generate languages which verify the stronger property of being semilinear. In, the operation of IO-substitution was created so as to exhibit mildly-context sensitive classes of languages which are not semilinear. In the present article, we extend (...) the notion of semilinearity, and characterize the Parikh image of the languages in IO, the closure of a class L of semilinear languages under IO-substitution, as universally-semilinear. Based on this result and on the work of Fischer on macro-grammars, we then show that IO is not closed under inverse homomorphism when L is closed under inverse homomorphism, and encompasses the class of regular languages. This result proves that IO is not a full AFL, where \ denotes the class of multiple context-free languages, closing an open question in Bourreau et al.. More importantly, our proof gives an insight into the relation between the non-closure under inverse homomorphism of \}\) and how IO-substitution breaks semilinearity. (shrink)

If all dependent expressions were adjacent some variety of immediate constituent analysis would suffice for grammar, but syntactic and semantic mismatches are characteristic of natural language; indeed this is a, or the, central problem in grammar. Logical categorial grammar reduces grammar to logic: an expression is well-formed if and only if an associated sequent is a theorem of a categorial logic. The paradigmatic categorial logic is the Lambek calculus, but being a logic of concatenation the Lambek calculus can only capture (...) discontinuous dependencies when they are peripheral. In this paper we present the displacement calculus, which is a logic of intercalation as well as concatenation and which subsumes the Lambek calculus. On the empirical side, we apply the new calculus to discontinuous idioms, quantification, VP ellipsis, medial extraction, pied-piping, appositive relativisation, parentheticals, gapping, comparative subdeletion, cross-serial dependencies, reflexivization, anaphora, dative alternation, and particle shift. On the technical side, we prove that the calculus enjoys Cut-elimination. (shrink)

Theories of natural language syntax often characterize grammatical knowledge as a form of abstract computation. This paper argues that such a characterization is correct, and that fundamental properties of grammar can and should be understood in terms of restrictions on the complexity of possible grammatical computation, when defined in terms of generative capacity. More specifically, the paper demonstrates that the computational restrictiveness imposed by Tree Adjoining Grammar provides important insights into the nature of human grammatical knowledge.

Four different kinds of grammars that can define crossing dependencies in human language are compared here: (i) context sensitive rewrite grammars with rules that depend on context, (ii) matching grammars with constraints that filter the generative structure of the language, (iii) copying grammars which can copy structures of unbounded size, and (iv) generating grammars in which crossing dependencies are generated from a finite lexical basis. Context sensitive rewrite grammars are syntactically, semantically and computationally unattractive. Generating grammars have a collection of (...) nice properties that ensure they define only “mildly context sensitive” languages, and Joshi has proposed that human languages have those properties too. But for certain distinctive kinds of crossing dependencies in human languages, copying or matching analyses predominate. Some results relevant to the viability of mildly context sensitive analyses and some open questions are reviewed. (shrink)

In his oft-cited, if rarely read book, Noam Chomsky ventured to propose a hierarchy of formal grammars. He defined them as rules for rewriting strings of terminal and nonterminal symbols into different strings of terminal and nonterminal symbols, thus giving birth to what is today known as the Chomsky hierarchy. The author himself claimed the theory applied exclusively to formal languages, but in his considerations he also happened to formulate a problem relating to natural languages, namely, to which formal grammar (...) category descriptive grammars of natural languages belong? While restraining from siding with any answer to the problem, Chomsky sparked a long philosophical and linguistic discussion revolving around complex structures in natural languages. (shrink)

This paper argues for the hypothesis of direct compositionality (as in, e.g., Montague 1974), according to which the combinatory syntactic rules specify a set of well-formed expressions while the semantic combinatory rules work in tandem to directly supply a model-theoretic interpretation to each expression as it is "built" in the syntax. (This thus obviates the need for any level like LF and, concomitantly, for any rules mapping surface structures to such a level.) I focus here on one related group of (...) phenomena: the interaction of "paycheck" pronouns with Weak Crossover effects and i-within-i effects. These interactions were studied in Jacobson (1977) as they show up in Back-Peters sentences. There I argued that these interactions show that paycheck pronouns have a complex representation at LF; here I show that all of the observations in this earlier work are compatible with the hypothesis of direct compositionality. The key tool is the adoption of a variation-free semantics (a semantics which makes no use of variables as part of the semantic machinery). In addition to the general consequences for the syntax/semantics interface, there are two other main results. First, I provide new arguments for a variable-free semantics. For example, it will be shown that under this view the paycheck reading of a pronoun comes for free; most other theories posit additional mechanisms and/or an additional lexical meaning for pronouns, and thus paycheck and regular pronouns are only accidentally homophonous. Second, I reiterate one of the central points in Jacobson (1977): this is that the first pronoun in a Bach-Peters sentence is indeed a paycheck pronoun, and hence nothing special needs to be said about these sentences nor does any new machinery need to be invoked for them. (shrink)