This paper defines the grammar class of sequentially indexed grammars. Sequentially indexed grammars are the result of a change in the index stack handling mechanism of indexed grammars [Aho68, Aho69]. Sequentially indexed grammars are different from linear indexed grammars [Gaz88]. Like indexed languages, sequentially indexed languages are a fully abstract language class. Unlike indexed languages, sequentially indexed languages allow polynomial parsing algorithms. We give a polynomial (...) algorithm for parsing with sequentially indexed gramamrs that is an extension of the Earley algorithm for parsing with context free grammars. (shrink)

Unification grammars are widely accepted as an expressive means for describing the structure of natural languages. In general, the recognition problem is undecidable for unification grammars. Even with restricted variants of the formalism, off-line parsable grammars, the problem is computationally hard. We present two natural constraints on unification grammars which limit their expressivity and allow for efficient processing. We first show that non-reentrant unification grammars generate exactly the class of context-free languages. We then relax the (...) constraint and show that one-reentrant unification grammars generate exactly the class of mildly context-sensitive languages. We thus relate the commonly used and linguistically motivated formalism of unification grammars to more restricted, computationally tractable classes of languages. (shrink)

We review the properties of Global Index Grammars (GIGs), a grammar formalism that uses a stack of indices associated with productions and has restricted context-sensitive power. We show how the control of the derivation is performed and how this impacts in the descriptive power of this formalism both in the string languages and the structural descriptions that GIGs can generate.

This paper extends the Earley parsing algorithm for context free languages [3] to the case of sequentially indexed languages. Sequentially indexed languages are related to indexed languages [1, 2]. The difference is that parallel processing of index stacks is replaced by sequential processing [4].

Like proper names, demonstratives, and definite descriptions, pronouns have referential uses. These can be 'essentially indexical' in the sense that they cannot be replaced by non-pronominal forms of reference. Here we show that the grammar of pronouns in such occurrences is systematically different from that of other referential expressions, in a way that illuminates the differences in reference in question. We specifically illustrate, in the domain of Romance clitics and pronouns, a hierarchy of referentiality, as related to the topology of (...) the grammatical phase. Our explanation is based on extending the 'Topological Mapping Hypotheses' of Longobardi and Sheehan & Hinzen. The extended topology covers the full range of interpretations, from purely predicative to quantificational, to referential and deictic. Along this scale, grammatical complexity increases, and none of these forms of reference is lexical. This provides evidence for the foundational conclusion that the source of essential indexicality is grammatical rather than lexical, semantic or pragmatic. (shrink)

Harmonic Grammar (HG) is a model of linguistic constraint interaction in which well-formedness is calculated as the sum of weighted constraint violations. We show how linear programming algorithms can be used to determine whether there is a weighting for a set of constraints that fits a set of linguistic data. The associated software package OT-Help provides a practical tool for studying large and complex linguistic systems in the HG framework and comparing the results with those of OT. We describe (...) the translation from Harmonic Grammars to systems solvable by linear programming, and we illustrate the usefulness of OT-Help with a set of studies of the predictions HG makes for phonological typology. (shrink)

This commentary discusses the division of labor between syntax and phonology, starting with the parallel model of grammar developed by Jackendoff. It is proposed that linear, left-to-right order of linguistic items is not represented in syntax, but in phonology. Syntax concerns the abstract relations of categories alone. All components of grammar contribute to linear order, by means of the interface rules.

This book answers both the 'what' and the 'why' question raised by indexical shift in crosslinguistic perspective. What are the possible profiles of an indexical shifting language, and why do we find these profiles and not various equally conceivable others? Drawing both from the literature (published and unpublished) and from original fieldwork on the language Nez Perce, Amy Rose Deal puts forward several major generalizations about indexical shift crosslinguistically and present a theory that attempts to explain them. This account has (...) consequences for the way we think about the semantics of attitude verbs, the nature of contexts, the typology of first person, and the relationship between indexicals and logophors, of course along with numerous consequences for the analysis of particular languages (e.g. Nez Perce, Uyghur, Korean, English, Zazaki, Amharic, Mishar Tatar). The book contains numerous glossed examples from a range of languages (including a detailed description of Nez Perce indexical shift, based on original fieldwork, as described above); a bibliography; and an appendix providing grammatical background about Nez Perce. (shrink)

A probabilistic Chomsky–Schützenberger hierarchy of grammars is introduced and studied, with the aim of understanding the expressive power of generative models. We offer characterizations of the distributions definable at each level of the hierarchy, including probabilistic regular, context-free, (linear) indexed, context-sensitive, and unrestricted grammars, each corresponding to familiar probabilistic machine classes. Special attention is given to distributions on (unary notations for) positive integers. Unlike in the classical case where the "semi-linear" languages all collapse into the (...) regular languages, using analytic tools adapted from the classical setting we show there is no collapse in the probabilistic hierarchy: more distributions become definable at each level. We also address related issues such as closure under probabilistic conditioning. (shrink)

An Indexed Synopsis of the Grammar of Assent by John J. Toohey. This book is a reproduction of the original book published in 1906 and may have some imperfections such as marks or hand-written notes.

Our proposal is concerned with the relation between an aspect of phonology (linearization) and syntax.1 In the picture that we had in mind, the syntax is autonomous — "it does what it does" — but sometimes the result maps to an unusable phonological representation. In this sense, linearization acts logically as a filter on derivations. We know of no evidence that the syntax can predict which syntactic objects will be usable by the phonology, and we know of no clear evidence (...) that the phonology communicates this information to the syntax. In this sense, our proposal fits squarely into the tradition that Svenonius characterizes as the "mainstream".2 We thus attempted to identify certain deviant configurations that are not plausibly excluded for syntax-internal reasons, but are filtered out in the linearization process. (shrink)

Let H n be the linear heptagonal networks with 2 n heptagons. We study the structure properties and the eigenvalues of the linear heptagonal networks. According to the Laplacian polynomial of H n, we utilize the method of decompositions. Thus, the Laplacian spectrum of H n is created by eigenvalues of a pair of matrices: L A and L S of order numbers 5 n + 1 and 4 n + 1 n! / r! n − r!, respectively. (...) On the basis of the roots and coefficients of their characteristic polynomials of L A and L S, we get not only the explicit forms of Kirchhoff index but also the corresponding total number of spanning trees of H n. (shrink)

The equivalence of leaf languages of tree adjoining grammars and monadic linear context-free grammars was shown about a decade ago. This paper presents a proof of the strong equivalence of these grammar formalisms. Non-strict tree adjoining grammars and monadic linear context-free grammars define the same class of tree languages. We also present a logical characterisation of this tree language class showing that a tree language is a member of this class iff it is the (...) two-dimensional yield of an MSO-definable three-dimensional tree language. (shrink)

In this paper we show that the membership problem for second order non-linear Abstract Categorial Grammars is decidable. A consequence of that result is that Montague-like semantics yield to a decidable text generation problem. Furthermore the proof we propose is based on a new tool, Higher Order Intersection Signatures, which grasps statically dynamic properties of λ-terms and presents an interest in its own.

Semantic Indexicality shows how a simple syntax can be combined with a propositional language at the level of logical analysis. It is the adoption of such a base language which has not been attempted before, and it is this which constitutes the originality of the book. Cresswell's simple and direct style makes this book accessible to a wider audience than the somewhat specialized subject matter might initially suggest.

It is the aim of INDICES to document recent explorations in the various fields of philosophical logic and formal linguistics and their applications in other disciplines. The main emphasis of this series is on self-contained monographs covering particular areas of recent research and surveys of methods, problems, and results in all fields of inquiry where recourse to logical analysis and logical methods has been fruitful. INDICES will contain monographs dealing with the central areas of philosophical logic (extensional and intensional systems, (...) indexical logics, non-classical logics, philosophy of logic, etc.) as well as studies in which these systems are applied to specific issues in philosophy, in the formal semantics of natural languages, the foundations of linguistic theory, in computational linguistics, and in theoretical computer science. Constructive type theory was first presented in 1970, by the Swedish logician Per Martin-Lof. It has become one of the main approaches used in the foundations of mathematics and computer science. But it has remained relatively unknown among linguists and philosophers, although it provides a considerable extension of the concepts and techniques of logic. The book first gives an introduction to type theory from the point of view of linguistics and the philosophy of language. Type theory is then applied in the areas of quantification, anaphora, temporal reference, and the structure of text and discourse. By virtue of the type-theoretical concepts of proof object and context, various phenomena of dependence and progression in language can be discussed in precise terms, and several well-known problems can be solved. A categorial grammar is presented togenerate formally a fragment of English, together with an example of a computer implementation. (shrink)

In this paper we discuss a new perspective on the syntax-semantics interface. Semantics, in this new set-up, is not ‘read off’ from Logical Forms as in mainstream approaches to generative grammar. Nor is it assigned to syntactic proofs using a Curry-Howard correspondence as in versions of the Lambek Calculus, or read off from f-structures using Linear Logic as in Lexical-Functional Grammar (LFG, Kaplan & Bresnan [9]). All such approaches are based on the idea that syntactic objects (trees, proofs, fstructures) (...) are somehow prior and that semantics must be parasitic on those syntactic objects. We challenge this idea and develop a grammar in which syntax and semantics are treated in a strictly parallel fashion. The grammar will have many ideas in common with the (converging) frameworks of categorial grammar and LFG, but its treatment of the syntax-semantics interface is radically different. Also, although the meaning component of the grammar is a version of Montague semantics and although there are obvious affinities between Montague’s conception of grammar and the work presented here, the grammar is not compositional, in the sense that composition of meaning need not follow surface structure. (shrink)

A well‐established principle of language is that there is a preference for closely related words to be close together in the sentence. This can be expressed as a preference for dependency length minimization (DLM). In this study, we explore quantitatively the degree to which natural languages reflect DLM. We extract the dependencies from natural language text and reorder the words in such a way as to minimize dependency length. Comparing the original text with these optimal linearizations (and also with random (...) linearizations) reveals the degree to which natural language minimizes dependency length. Tests on English data show that English shows a strong effect of DLM, with dependency length much closer to optimal than to random; the optimal English grammar also has many specific features in common with English. In German, too, dependency length is significantly less than random, but the effect is much weaker than in English. We conclude by speculating about some possible reasons for this difference between English and German. (shrink)

Many variants of categorial grammar assume an underlying logic which is associative and linear. In relation to left extraction, the former property is challenged by island domains, which involve nonassociativity, and the latter property is challenged by parasitic gaps, which involve nonlinearity. We present a version of type logical grammar including ‘structural inhibition’ for nonassociativity and ‘structural facilitation’ for nonlinearity and we give an account of relativisation including islands and parasitic gaps and their interaction.

This paper introduces λ-grammar, a form of categorial grammar that has much in common with LFG. Like other forms of categorial grammar, λ-grammars are multi-dimensional and their components are combined in a strictly parallel fashion. Grammatical representations are combined with the help of linear combinators, closed pure λ-terms in which each abstractor binds exactly one variable. Mathematically this is equivalent to employing linear logic, in use in LFG for semantic composition, but the method seems more practicable.

Linear Syntax makes a case for a critical reassessment of the wide-spread view that syntax can be reduced to tree structures. It argues that a crucial part of the description of German clausal syntax should instead be based on concepts that are defined in terms of linear order. By connecting the descriptive tools of modern phrase-structure grammar with traditional descriptive scholarship, Andreas Kathol offers a new perspective on many long-standing problems in syntactic theory.

This book brings together classic and recent papers in the philosophical and linguistic analysis of fuzzy grammar, gradience in meaning, word classes, and syntax. Issues such as how many grains make a heap, when a puddle becomes a pond, and so forth, have occupied thinkers since Aristotle and over the last two decades been the subject of increasing interest among linguists as well as in fields such as artificial intelligence and computational linguistics. The work is designed to be of use (...) to students in all these fields. It has a substantial introduction, is divided into thematic parts, contains annotated sections of further reading, and is fully indexed. (shrink)

An original, theoretical work on cross-linguistic word order from a leading syntactician.

ABSTRACT This part of the series has a dual purpose. In the first place we will discuss two kinds of theories of proof. The first kind will be called a theory of linear proof. The second has been called a theory of suppositional proof. The term "natural deduction" has often and correctly been used to refer to the second kind of theory, but I shall not do so here because many of the theories so-called are not of the second (...) kind--they must be thought of either as disguised linear theories or theories of a third kind (see postscript below). The second purpose of this part is 25 to develop some of the main ideas needed in constructing a comprehensive theory of proof. The reason for choosing the linear and suppositional theories for this purpose is because the linear theory includes only rules of a very simple nature, and the suppositional theory can be seen as the result of making the linear theory more comprehensive. CORRECTION: At the time these articles were written the word ‘proof’ especially in the phrase ‘proof from hypotheses’ was widely used to refer to what were earlier and are now called deductions. I ask your forgiveness. I have forgiven Church and Henkin who misled me. (shrink)

This paper addresses a phenomenon in which certain word-parts can be omitted. The evidence shows that the full range of data cannot be captured by a sublexical analysis, since the phenomena can be observed both in phrasal and in lexical environments. It is argued that a form of deletion is involved, and that the phenomena—lexical or otherwise—are subject to the same phonological, semantic, and syntactic constraints. In the formalization that is proposed, all of the above constraints are cast in a (...) parallel and declarative fashion, in the framework of Head-Driven Phrase Structure Grammar (Pollard and Sag Head-driven phrase structure grammar, 1994), since the various levels of linguistic description are locally and simultaneously available. Building on recent accounts of ellipsis, this paper proposes a unified and general account of word-part ellipsis and phrasal ellipsis. (shrink)

Pregroup grammars have a cubic recognition algorithm. Here, we define a correct and complete recognition and parsing algorithm and give sufficient conditions for the algorithm to run in linear time. These conditions are satisfied by a large class of pregroup grammars, including grammars that handle coordinate structures and distant constituents.

This paper proposes an architecture for the mapping between syntax and phonology — in particular, that aspect of phonology that determines ordering. In Fox and Pesetsky (in prep.), we will argue that this architecture, when combined with a general theory of syntactic domains ("phases"), provides a new understanding of a variety of phenomena that have received diverse accounts in the literature. This shorter paper focuses on two processes, both drawn from Scandinavian: the familiar process of Object Shift and the less (...) well-known process of Quantifier Movement. We will argue that constraints on these operations can be seen as instances of the same property of grammar that explains the fact that movement is local and successive cyclic. We begin by sketching a model in which locality and successive cyclicity are consequences of the architecture that we propose, rather than specific facts about movement itself. We next present our proposal in somewhat greater detail, and show how it can account for a wide range of apparent limitations on movement — in particular, superficially contradictory restrictions on Object Shift and Quantifier Movement. The restrictions on Object Shift include those grouped under the rubric of Holmberg's Generalization, which Quantifier Movement does not seem to obey. We will argue that Quantifier Movement instead obeys a near mirror-image of Holmberg's Generalization (an "Inverse Holmberg Effect"), but that both Holmberg's Generalization and its mirror image are expected if our proposed architecture is correct. (shrink)

We reformulate minimalist grammars as partial functions on term algebras for strings and trees. Using filler/role bindings and tensor product representations, we construct homomorphisms for these data structures into geometric vector spaces. We prove that the structure-building functions as well as simple processors for minimalist languages can be realized by piecewise linear operators in representation space. We also propose harmony, i.e. the distance of an intermediate processing step from the final well-formed state in representation space, as a measure (...) of processing complexity. Finally, we illustrate our findings by means of two particular arithmetic and fractal representations. (shrink)

This chapter contains sections titled: The continuation of the Early Draft into philosophy of mathematics Hidden isomorphism A common methodology The flatness of philosophical grammar.

Grammar can be formulated as a kind of substructural propositional logic. In support of this claim, we survey bare Gentzen style deductive systems and two kinds of non-commutative linear logic: intuitionistic and compact bilinear logic. We also glance at their categorical refinements.

Lambek categorial grammars is a class of formal grammars based on the Lambek calculus. Pentus proved in 1993 that they generate exactly the class of context-free languages without the empty word. In this paper, we study categorial grammars based on the Lambek calculus with the permutation rule LP. Of particular interest is the product-free fragment of LP called the Lambek-van Benthem calculus LBC. Buszkowski in his 1984 paper conjectured that grammars based on the Lambek-van Benthem calculus (...) (LBC-grammars for short) generate exactly permutation closures of context-free languages. In this paper, we disprove this conjecture by presenting a language generated by an LBC-grammar that is not a permutation closure of any context-free language. Firstly, we introduce an ad-hoc modification of vector addition systems called linearly-restricted branching vector addition systems with states and additional memory (LRBVASSAMs for short) and prove that the latter are equivalent to LBC-grammars. Then we construct an LRBVASSAM that generates a non-semilinear set and thus disprove Buszkowski’s conjecture. Since Buszkowski’s conjecture is false, not so much is known about the languages generated by LBC-grammars or by LP-grammars. The equivalence of LRBVASSAMs and LBC-grammars allows us to establish a number of their properties. We show that LP-grammars generate the same class of languages as LBC-grammars; that is, removing product from LP does not decrease expressive power of corresponding categorial grammars. We also prove that this class of languages is closed under union, intersection, concatenation, and Kleene plus. (shrink)

Generalized linear mixed models estimate fixed and random effects and are especially useful when the dependent variable is binary, ordinal, count or quantitative but not normally distributed. They are also useful when the dependent variable involves repeated measures, since GLMMs can model autocorrelation. This study aimed to determine how and how often GLMMs are used in psychology and to summarize how the information about them is presented in published articles. Our focus in this respect was mainly on frequentist models. (...) In order to review studies applying GLMMs in psychology we searched the Web of Science for articles published over the period 2014–2018. A total of 316 empirical articles were selected for trend study from 2014 to 2018. We then conducted a systematic review of 118 GLMM analyses from 80 empirical articles indexed in Journal Citation Reports during 2018 in order to evaluate report quality. Results showed that the use of GLMMs increased over time and that 86.4% of articles were published in first- or second-quartile journals. Although GLMMs have, in recent years, been increasingly used in psychology, most of the important information about them was not stated in the majority of articles. Report quality needs to be improved in line with current recommendations for the use of GLMMs. (shrink)

This paper proposes an architecture for the mapping between syntax and phonology — in particular, that aspect of phonology that determines ordering. In Fox and Pesetsky (in prep.), we will argue that this architecture, when combined with a general theory of syntactic domains ("phases"), provides a new understanding of a variety of phenomena that have received diverse accounts in the literature. This shorter paper focuses on two processes, both drawn from Scandinavian: the familiar process of Object Shift and the less (...) well-known process of Quantifier Movement. We will argue that constraints on these operations can be seen as instances of the same property of grammar that explains the fact that movement is local and successive cyclic. We begin by sketching a model in which locality and successive cyclicity are consequences of the architecture that we propose, rather than specific facts about movement itself. We next present our proposal in somewhat greater detail, and show how it can account for a wide range of apparent limitations on movement — in particular, superficially contradictory restrictions on Object Shift and Quantifier Movement. The restrictions on Object Shift include those grouped under the rubric of Holmberg's Generalization, which Quantifier Movement does not seem to obey. We will argue that Quantifier Movement instead obeys a near mirror-image of Holmberg's Generalization (an "Inverse Holmberg Effect"), but that both Holmberg's Generalization and its mirror image are expected if our proposed architecture is correct. (shrink)

The objectives of this paper are twofold. The first is to present a differentiation between two kinds of deferred uses of indexicals: those in which indexical utterances express singular propositions (I term them deferred reference proper) and those where they express general propositions (called descriptive uses of indexicals). The second objective is the analysis of the descriptive uses of indexicals. In contrast to Nunberg, who treats descriptive uses as a special case of deferred reference in which a property contributes to (...) the proposition expressed, I argue that examples in which a general proposition is indeed expressed by an indexical cannot be treated by assuming that the property is a deferred referent of the pronoun. I propose an analysis of descriptive uses of indexicals by means of a pragmatic mechanism of ‘descriptive anaphora’, which attempts to explain the special kind of contribution of the property retrieved from the context to the proposition that is characteristic of the descriptive interpretation. (shrink)

The paper presents a way to transform pregroup grammars into contextfree grammars using functional composition. The same technique can also be used for the proof-nets of multiplicative cyclic linear logic and for Lambek calculus allowing empty premises.

On the basis of an experimental investigation of the construals of present under past in child French, we argue that French children, just like Japanese adult speakers, but unlike French adult speakers, allow pure simultaneous construals of present under past, where the present denotes an interval that lies completely in the past, be it in relative or complement clauses. We conclude that French children have two presents: an indexical present and a zero present (just like Japanese adults, cf. Ogihara 1999, (...) 2008), suggesting that French children have both the Japanese and the French setting for the Sequence of Tense parameter since they allow simultaneous construals of both present and past under past. This multiple grammar approach to tense interpretation in child French extends to child Japanese in so far as Japanese children have been argued to allow simultaneous readings of past under past, although this reading is unavailable in the target grammar (Matsuo & Hollebrandse 1999). (shrink)

Lautemann et al. (1995) gave a descriptive characterisation of the class of context-free languages, showing that a language is context-free iff it is definable as the set of words satisfying some sentence of a particular logic (fragment) over words. The present notes discuss how to specialise this result to the class of linear languages. Somewhat surprisingly, what would seem the most straightforward specialisation actually fails, due to the fact that linear grammars fail to admit a Greibach normal (...) form. We identify an alternative specialisation, based on an alternative characterisation of context-free languages, also noted by Lautemann et al. (1995). (shrink)

Second-order abstract categorial grammars (de Groote in Association for computational linguistics, 39th annual meeting and 10th conference of the European chapter, proceedings of the conference, pp. 148–155, 2001) and hyperedge replacement grammars (Bauderon and Courcelle in Math Syst Theory 20:83–127, 1987; Habel and Kreowski in STACS 87: 4th Annual symposium on theoretical aspects of computer science. Lecture notes in computer science, vol 247, Springer, Berlin, pp 207–219, 1987) are two natural ways of generalizing “context-free” grammar formalisms for string (...) and tree languages. It is known that the string generating power of both formalisms is equivalent to (non-erasing) multiple context-free grammars (Seki et al. in Theor Comput Sci 88:191–229, 1991) or linear context-free rewriting systems (Weir in Characterizing mildly context-sensitive grammar formalisms, University of Pennsylvania, 1988). In this paper, we give a simple, direct proof of the fact that second-order ACGs are simulated by hyperedge replacement grammars, which implies that the string and tree generating power of the former is included in that of the latter. The normal form for tree-generating hyperedge replacement grammars given by Engelfriet and Maneth (Graph transformation. Lecture notes in computer science, vol 1764. Springer, Berlin, pp 15–29, 2000) can then be used to show that the tree generating power of second-order ACGs is exactly the same as that of hyperedge replacement grammars. (shrink)

(2) Type Logical Grammar (Moortgat & Oehrle 1994, Morrill 1994. Moortgat 1996): i. Grammar as a deductive system; variant of linear logic; two deductive rules for each type constructor (=; n; ): elimination ( modus ponens) and introduction ( rule of conditional proof).

This paper offers an analysis of indexical expressions and proper names as they are used in proverbs. Both indexicals and proper names contribute properties rather than objects to the propositions expressed when they are used in sentences interpreted as proverbs. According to the proposal, their contribution is accounted for by the mechanism of descriptive anaphora. Indexicals with rich linguistic meaning, such as ‘I’, ‘you’ or ‘today’, turn out to be cases of the attributive uses of indexicals, i.e. uses whose contribution (...) relies on the linguistic meaning of the word. Third person pronouns, names of locations as well as surnames are analyzed as non-attributive descriptive uses. (shrink)