Head-driven phrase structure grammar (HPSG) is one of the most prominent theories employed in deep parsing of natural language. Many linguistic theories are arguably best formalized in extensions of modal or dynamic logic (Keller, Feature logics, infinitary descriptions and grammar, 1993; Kracht, Linguistics Philos 18:401–458, 1995; Moss and Tiede, In: Blackburn, van Benthem, and Wolther (eds.) Handbook of modal logic, 2006), and HPSG seems to be no exception. Adequate extensions of dynamic logic have not been studied in detail, however; the (...) most important aspect is the reference to sets of substructures. In this paper, an adequate extension is identified, and some important results are established: Satisfiability is highly undecidable, and model checking is shown to be in EXPTIME and PSPACE-hard. A fragment with polynomial time model checking procedures is identified; it is shown to cover considerable fragments of HPSG. (shrink)

‘Case’ and ‘grammatical relations’ are central to syntactic theory, but rigorous treatments of these concepts in surface-oriented grammars such as Dynamic Syntax are pending. In this respect, Japanese is worthy of mention; in this language, the nominative case particle ga, which typically marks a subject, may mark an object in certain syntactic contexts, and more than one instance of ga may be present within a single clause. These patterns cannot be captured if we simply assume that ga marks a subject. (...) In the present article, we aim to advance formal aspects of the framework, especially the mechanism of ‘structural underspecification,’ by proposing that the parse of a case particle maximally excludes potential landing sites of an unfixed node at the time of parsing the case particle, delaying the resolution of the unfixed node until a subsequent stage of structure building. This maximal exclusion approach to structural underspecification accounts for a range of case marking patterns and their connections with grammatical relations. (shrink)

‘Case’ and ‘grammatical relations’ are central to syntactic theory, but rigorous treatments of these concepts in surface-oriented grammars such as Dynamic Syntax are pending. In this respect, Japanese is worthy of mention; in this language, the nominative case particle ga, which typically marks a subject, may mark an object in certain syntactic contexts, and more than one instance of ga may be present within a single clause. These patterns cannot be captured if we simply assume that ga marks a subject. (...) In the present article, we aim to advance formal aspects of the framework, especially the mechanism of ‘structural underspecification,’ by proposing that the parse of a case particle maximally excludes potential landing sites of an unfixed node at the time of parsing the case particle, delaying the resolution of the unfixed node until a subsequent stage of structure building. This maximal exclusion approach to structural underspecification accounts for a range of case marking patterns and their connections with grammatical relations. (shrink)

‘Case’ and ‘grammatical relations’ are central to syntactic theory, but rigorous treatments of these concepts in surface-oriented grammars such as Dynamic Syntax are pending. In this respect, Japanese is worthy of mention; in this language, the nominative case particle ga, which typically marks a subject, may mark an object in certain syntactic contexts, and more than one instance of ga may be present within a single clause. These patterns cannot be captured if we simply assume that ga marks a subject. (...) In the present article, we aim to advance formal aspects of the framework, especially the mechanism of ‘structural underspecification,’ by proposing that the parse of a case particle maximally excludes potential landing sites of an unfixed node at the time of parsing the case particle, delaying the resolution of the unfixed node until a subsequent stage of structure building. This maximal exclusion approach to structural underspecification accounts for a range of case marking patterns and their connections with grammatical relations. (shrink)

Japanese exhibits the Multiple Nominative Construction (MNC), where more than one nominative-marked NP appear within a single clause. Though the MNC has been extensively investigated in the syntax literature, its relation to rightward-displacement constructions has hardly been discussed. In the present article, we provide new sets of MNC data relating to the three types of right-displacement constructions: relatives, clefts, and postposing. The generalisation is that for the linearly ordered nominative-marked NPs in an MNC string, only the leftmost NP may be (...) right-displaced (that is, relativised, clefted, postposed). This pattern is shown to follow as an outcome of modelling incremental parsing, without stipulations specifically made for the observed data. We propose an account of MNCs in the light of an incremental grammar, formalising it within Dynamic Syntax. In this account, an MNC sentence is parsed on a word-by-word basis, and its interpretation is gradually built up, modelled as the growth of a semantic structure. In cases where a right-displacement is permitted, the right-displaced NP is successfully parsed against the structure built by the preceding part of the sentence. In cases where a right-displacement is disallowed, the right-displaced NP cannot be properly processed because the preceding part of the sentence has created no structural position into which the content of the right-displaced NP is reflected. As theoretical implications of the proposed account, we suggest the concept of time-linear grammaticality. (shrink)

Se presentan los aspectos básicos de un modelo de procesamiento sintáctico-semántico denominado Sintaxis Dinámica. Para cumplir con este objetivo, presentamos definiciones e ilustraciones de los componentes esenciales del metalenguaje, y ejemplificamos este modelamiento dinámico presentando el proceso sintáctico completo de composición del significado de una oración simple. Finalmente, se señalan sucintamente algunas características prominentes del modelo.

We sketch an axiomatic reformalization of Generalized Phrase StructureGrammar (GPSG) – a definition purely within the language ofmathematical logic of the theory GPSG embodies. While this treatment raisesa number of theoretical issues for GPSG, our focus is not thereformalization itself but rather the method we employ. The model-theoreticapproach it exemplifies can be seen as a natural step in the evolution ofconstraint-based theories from their grammar-based antecedents. One goal ofthis paper is to introduce this approach to a broader audience and todemonstrate (...) its application to an existing theory. As such, it joins agrowing literature of similar studies. Prior studies, however, have had anumber of weaknesses – they generally offer little in the way ofconcrete examples of the advantages the approach has to offer, theytypically ignore significant portions of the theories they address, and, byfully abstracting away from the notion of grammar mechanism, they largelyabandon the possibility of establishing meaningful complexity results. Thesecond goal of the paper is to address these issues. Our thrust is to sketchthe reformalization sufficiently to illustrate the way in which it capturesFeature Specification Defaults (FSDs) and the Exhaustive Constant PartialOrdering (ECPO) property. Our definition of FSDs is considerably simplifiedrelative to the original formalization and is free of the procedural flavorthat has led some to assume that FSDs are inherently dynamic. Our treatmentof ECPO uncovers a gap in its definition in the context of partialcategories that has heretofore gone unnoticed. We offer these as ademonstration of the kind of insight that a model-theoretic reinterpretationcan bring to an existing theory. Further, since these are the types ofproperties that prior studies in this genre have failed to address, FSDs andECPO provide a means for us to explore the limitations of these approachesand to offer ways of overcoming them. Finally, the logical framework weemploy has a well defined generative capacity – definability in thisframework characterizes strong context-freeness in a particular sense. Thus,despite being more abstract than its constraint-based predecessors, themodel-theoretic approach, as exemplified here, can offer stronger complexityresults than are typically available in the constraint-based framework. (shrink)

In this paper, I address the issue of scientific modelling in contemporary linguistics, focusing on the generative tradition. In so doing, I identify two common varieties of linguistic idealisation, which I call determination and isolation respectively. I argue that these distinct types of idealisation can both be described within the remit of Weisberg’s :639–659, 2007) minimalist idealisation strategy in the sciences. Following a line set by Blutner :27–35, 2011), I propose this minimalist idealisation analysis for a broad construal of the (...) generative linguistic programme and thus cite examples from a wide range of linguistic frameworks including early generative syntax, Minimalism, the parallel architecture and optimality theory. Lastly, I claim that from a modelling perspective, the dynamic turn in syntax can be explained as a continuation, as opposed to a marked shift, of the generative modelling paradigm. Seen in this light, my proposal is an even broader construal of the generative tradition, along scientific modelling lines. Thus, I offer a lens through which to appreciate the scientific contribution of generative grammar, amid an increased resistance to some of its core theoretical posits, in terms of a brand of structural realism in the philosophy of science and specifically scientific modelling. (shrink)

This paper shows Korean speakers’ strong preference for incremental structure building based on the following core phenomena: left–right asymmetry; pre-verbal structure building and a strong preference for early association. This paper argues that these phenomena reflect the procedural aspects of linguistic competence, which are difficult to explain within non-procedural grammar formalisms. Based on these observations, I argue for the necessity of a grammar formalism that adopts left-to-right incrementality as a core property of the syntactic architecture. In particular, I aim to (...) show the role of constructive particles; prosody; and structural routines in incremental Korean structure building. Though the nature of this discussion is theory-neutral, in order to formalise this idea I will adopt Dynamic Syntax [DS: Kempson et al. ; Cann et al. ] in this paper. (shrink)

Feedback such as backchannels and clarification requests often occurs subsententially, demonstrating the incremental nature of grounding in dialogue. However, although such feedback can occur at any point within an utterance, it typically does not do so, tending to occur at Feedback Relevance Spaces. We present a corpus study of acknowledgements and clarification requests in British English, and describe how our low-level, semantic processing model in Dynamic Syntax accounts for this feedback. The model trivially accounts for the 85% of cases where (...) feedback occurs at FRSs, but we also describe how it can be integrated or interpreted at non-FRSs using the predictive, incremental and interactive nature of the formalism. This model shows how feedback serves to continually realign processing contexts and thus manage the characteristic divergence and convergence that is key to moving dialogue forward. (shrink)

Dynamic Syntax is an action-based grammar formalism which models the process of natural language understanding as monotonic tree growth. This paper presents an introduction to the notions of incrementality and underspecification and update, drawing on the assumptions made by DS. It lays out the tools of the theoretical framework that are necessary to understand the accounts developed in the other contributions to the Special Issue. It also represents an up-to-date account of the framework, combining the developments that have previously remained (...) distributed in a diverse body of literature. (shrink)

This paper gives a simple method for providing categorial brands of feature-based unification grammars with a model-theoretic semantics. The key idea is to apply the paradigm of fibred semantics (or layered logics, see Gabbay (1990)) in order to combine the two components of a feature-based grammar logic. We demonstrate the method for the augmentation of Lambek categorial grammar with Kasper/Rounds-style feature logic. These are combined by replacing (or annotating) atomic formulas of the first logic, i.e. the basic syntactic types, by (...) formulas of the second. Modelling such a combined logic is less trivial than one might expect. The direct application of the fibred semantics method where a combined atomic formula like np (num: sg & pers: 3rd) denotes those strings which have the indicated property and the categorial operators denote the usual left- and right-residuals of these string sets, does not match the intuitive, unification-based proof theory. Unification implements a global bookkeeping with respect to a proof whereas the direct fibring method restricts its view to the atoms of the grammar logic. The solution is to interpret the (embedded) feature terms as global feature constraints while maintaining the same kind of fibred structures. For this adjusted semantics, the anticipated proof system is sound and complete. (shrink)

In this paper, the historical development of the clitic systems of Standard Modern, Cypriot and Pontic Greek is discussed. These three varieties not only present the whole range of variation one can find across clitic systems in Greek but, furthermore, derive from a common linguistic ancestor, i.e. Koine Greek. This paper argues that the transition from Koine Greek to the Medieval varieties and from the Medieval varieties to the respective modern ones can be explained by making the assumption that routinisation (...) and parsing/hearer assymetries are two important factors behind syntactic change. The claim is that the transition from Koine to the Medieval Greek varieties involves the emergence of a clitic system with encoded syntactic constraints out of a freer one, where clitic positioning was regulated by pragmatic preferences rather than syntactic constraints. Then, the transition to the modern varieties from the respective medieval ones is explained, at least partly, on the assumption that production/parsing mismatches are capable of triggering syntactic change. This last assumption combined with: the tendency to obtain more generalised parsing triggers for parsing the individual clitics and the fact that the Medieval varieties in question differ in minimal but crucial ways, provides us an explanation for the transition to the modern varieties. (shrink)

In this paper we adopt the hypothesis that languages are mechanisms for interaction, and that grammars encode the means by which such interaction may take place, by use of procedures that construct representations of meaning from strings of words uttered in context, and conversely strings of words are built up from representations of content in interaction with context. In a review of the systemic use of ellipsis in dialogue and associated split-utterance phenomena, we show how, in Dynamic Syntax, words give (...) rise to a range of procedures for the building of representations of the content of some utterance, which both speakers and hearers use. We then extend the discussion to take account of adjuncts, showing how they contribute to content construction both in single utterances and across speakers. The same mechanisms are then shown to underlie the building of inferential extensions of meaning in context, giving rise to the creation of the ad hoc concepts expressed by phrases or single words in relation to the utterance context and ultimately to the creation of metaphorical uses of language. (shrink)

We provide first-order axioms for the theories of finite trees with bounded branching and finite trees with arbitrary (finite) branching. The signature is chosen to express, in a natural way, those properties of trees most relevant to linguistic theories. These axioms provide a foundation for results in linguistics that are based on reasoning formally about such properties. We include some observations on the expressive power of these theories relative to traditional language complexity classes.

This paper is about a special version of PDL, proposed by Marcus Kracht, for reasoning about sibling ordered trees. It has four basic programs corresponding to the child, parent, left- and right-sibling relations in such trees. The original motivation for this language is rooted in the field of model-theoretic syntax. Motivated by recent developments in the area of semi-structured data, and, especially, in the field of query languages for XML (eXtensible Markup Language) documents, we revisit the language. This renewed interest (...) comes with a special focus on complexity and expressivity aspects of the language, aspects that have so far largely been ignored. We survey and derive complexity results, and spend most of the paper on the most important open question concerning the language: what is its expressive power? We approach this question from two angles: Which first-order properties can be expressed? And which second-order properties? While we are still some way from definitive answers to these questions, we discuss two first-order fragments of the PDL language for ordered trees, and show how the language can be used to express some typical (second-order) problems, like the boolean circuit and the frontier problem. (shrink)

Preference is a basic notion in human behaviour, underlying such varied phenomena as individual rationality in the philosophy of action and game theory, obligations in deontic logic (we should aim for the best of all possible worlds), or collective decisions in social choice theory. Also, in a more abstract sense, preference orderings are used in conditional logic or non-monotonic reasoning as a way of arranging worlds into more or less plausible ones. The field of preference logic (cf. Hansson [10]) studies (...) formal systems that can express and analyze notions of preference between various sorts of entities: worlds, actions, or propositions. The art is of course to design a language that combines perspicuity and low complexity with reasonable expressive power. In this paper, we take a particularly simple approach. As preferences are binary relations between worlds, they naturally support standard unary modalities. In particular, our key modality ♦ϕ will just say that is ϕ true in some world which is at least as good as the current one. Of course, this notion can also be indexed to separate agents. The essence of this language is already in [4], but our semantics is more general, and so are our applications and later language extensions. Our modal language can express a variety of preference notions between propositions. Moreover, as already suggested in [9], it can “deconstruct” standard conditionals, providing an embedding of conditional logic into more standard modal logics. Next, we take the language to the analysis of games, where some sort of preference logic is evidently needed ([23] has a binary modal analysis different from ours). We show how a qualitative unary preference modality suffices for defining Nash Equilibrium in strategic games, and also the Backward Induction solution for finite extensive games. Finally, from a technical perspective, our treatment adds a new twist. Each application considered in this paper suggests the need for some additional access to worlds before the preference modality can unfold its true power.. (shrink)