Unification grammars are known to be Turing-equivalent; given a grammar G and a word w, it is undecidable whether w L(G). In order to ensure decidability, several constraints on grammars, commonly known as off-line parsability (OLP), were suggested, such that the recognition problem is decidable for grammars which satisfy OLP. An open question is whether it is decidable if a given grammar satisfies OLP. In this paper we investigate various definitions of OLP and discuss their interrelations, proving that (...) some of the OLP variants are indeed undecidable. We then present a novel, decidable OLP constraint which is more liberal than the existing decidable ones. (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 provide an algorithm for determining a categorial grammar from linguistic data that essentially uses unification of type-schemes assigned to atoms. The algorithm presented here extends an earlier one restricted to rigid categorial grammars, introduced in [4] and [5], by admitting non-rigid outputs. The key innovation is the notion of an optimal unifier, a natural generalization of that of a most general unifier.

A method is described for inducing a type-logical grammar from a sample of bare sentence trees which are annotated by lambda terms, called term-labelled trees . Any type logic from a permitted class of multimodal logics may be specified for use with the procedure, which induces the lexicon of the grammar including the grammatical categories. A first stage of semantic bootstrapping is performed, which induces a general form lexicon from the sample of term-labelled trees using Fulop’s (J Log (...) Lang Inf 14(1):49–86, 2005) procedure. Next we present a two-stage procedure for performing distributional learning by unifying the lexical types that are initially discovered. The first structural unification algorithm in essence unifies the initial family of sets of types so that the resulting grammar will generate all term-labelled trees that follow the usage patterns evident from the learning sample. Further altering the lexical categories to generate a recursively extended language can be accomplished by a second unification. The combined unification algorithm is shown to yield a new type-logical lexicon that extends the learning sample to a possibly infinite (and possibly context-sensitive) language in a principled fashion. Finally, the complete learning strategy is analyzed from the perspective of algorithmic learning theory; the range of the procedure is shown to be a class of term-labelled tree languages which is finitely learnable from good examples (Lange et al in Algorithmic learning theory, Vol 872 of lecture notes in artificial intelligence, Springer, Berlin, pp 423–437), and so is identifiable in the limit as a corollary. (shrink)

In this paper the notion of unifier is extended to the infinite set case. The proof of existence of the most general unifier of any infinite, unifiable set of types (terms) is presented. Learning procedure, based on infinite set unification, is described.

This article introduces Agentive Cognitive Construction Grammar, an emerging field that seeks to connect the linguistic system with speaker-meaning. The stated purpose is thus to tackle a pervasive disconnect in both cognitive linguistics and construction grammar, whereby the linguistic system and speaker selections are separated in the belief that language is essentially a mental process associated with the brain, and hence, separated from bodily experience. I contend this view by introducing a triadic model of construction in which form (...) and function are inextricably bound up with agency. This is possible because language is tethered to senses of movement and balance that connect experiences with the physical world with the mental. A major insight of the paper is that argument structure constructions partake of both linguistic and non-linguistic signs, which provides speakers with a means to verbalize their thoughts and distribute agency in specific events. (shrink)

Polarized unification grammar (PUG) is a linguistic formalism which uses polarities to better control the way grammar fragments interact. The grammar combination operation of PUG was conjectured to be associative. We show that PUG grammar combination is not associative, and even attaching polarities to objects does not make it order-independent. Moreover, we prove that no non-trivial polarity system exists for which grammar combination is associative. We then redefine the grammar combination operator, moving to the (...) powerset domain, in a way that guarantees associativity. The method we propose is general and is applicable to a variety of tree-based grammar formalisms. (shrink)

Cognitive science is an interdisciplinary conglomerate of various research fields and disciplines, which increases the risk of fragmentation of cognitive theories. However, while most previous work has focused on theoretical integration, some kinds of integration may turn out to be monstrous, or result in superficially lumped and unrelated bodies of knowledge. In this paper, I distinguish theoretical integration from theoretical unification, and propose some analyses of theoretical unification dimensions. Moreover, two research strategies that are supposed to lead to unification are (...) analyzed in terms of the mechanistic account of explanation. Finally, I argue that theoretical unification is not an absolute requirement from the mechanistic perspective, and that strategies aiming at unification may be premature in fields where there are multiple conflicting explanatory models. (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)

One of the consequences of improper management of European businesses, set solely on profit, is the global financial crisis, felt even today by many societies. Previous negative experience has led to a growing interest in the world at present, in the model in which employees are guaranteed involvement in the management of transnational entities. A new, universal legal framework for the functioning of this model has been created by the European Union. Instead of creating a single transnational legal system, it (...) was decided to create a model for employee involvement in management by coordinating national systems. The aim of this study is to analyse the terminology related to the issue of workers’ involvement in the management of European business entities. This analysis will aim to determine whether the legal language used in the EU regulations and directives relating to workers’ involvement in management and implementing acts allows coordination between legal systems of the Member States. In this context, it is particularly important to determine whether the terminology used in EU acts is consistent with the terminology used in Polish implementing laws and how EU terminology fits into current understanding in the Polish legal tradition of institutions of employee involvement in the management of the workplace. (shrink)

Higher order unification is a way of combining information (or equivalently, solving equations) expressed as terms of a typed higher order logic. A suitably restricted form of the notion has been used as a simple and perspicuous basis for the resolution of the meaning of elliptical expressions and for the interpretation of some non-compositional types of comparative construction also involving ellipsis. This paper explores another area of application for this concept in the interpretation of sentences containing intonationally marked focus, or (...) various semantic constructs which are sensitive to focus.Similarities and differences between this approach, and theories using alternative semantics, structured meanings, or flexible categorial grammars, are described. The paper argues that the higher order unification approach offers descriptive advantages over these alternatives, as well as the practical advantage of being capable of fairly direct computational implementation. (shrink)

This paper investigates whether the fundamental linguistic insights and intuitions of Lexical Functional Grammar, which is usually presented as a constraint-based linguistic theory, can be reformulated in a resource sensitive framework using a substructural modal logic. In the approach investigated here, LFG's f-descriptions are replaced with expressions from a multi-modal propositional logic. In effect, the feature structure unification basis of LFG's f-structures is replaced with a very different resource based mechanism. It turns out that some linguistic analyses that required (...) non-monotonic devices in LFG analysis of Icelandic) can be straightforwardly expressed in the framework presented here. Moreover, a Curry– Howard correspondence between proofs in this logic and -terms provides a semantic interpretation as a by-product of the process of showing syntactic well-formedness. (shrink)

This paper develops a framework for TAG (Tree Adjoining Grammar) semantics that brings together ideas from different recent approaches. Then, within this framework, an analysis of scope is proposed that accounts for the different scopal properties of quantifiers, adverbs, raising verbs and attitude verbs. Finally, including situation variables in the semantics, different situation binding possibilities are derived for different types of quantificational elements.

Chomsky's current Biolinguistic methodology is shown to comport with what might be called 'established' aspects of biological method, thereby raising, in the biolinguistic domain, issues concerning biological autonomy from the physical sciences. At least current irreducibility of biology, including biolinguistics, stems in at least some cases from the very nature of what I will claim is physiological, or inter-organ/inter-component, macro-levels of explanation which play a new and central explanatory role in Chomsky's inter-componential explanation of certain properties of the syntactic component (...) of Universal Grammar. Under this new mode of explanation, certain physiological functions of cognitive mental organs are hypothesized, in an attempt to explain aspects of their internal anatomy. Thus, the internal anatomy of the syntactic component exhibits features that enable it to effectively interface with other 'adjacent' organs, such as the Conceptual-Intensional system and the Sensory- Motor system. These two interface systems take as their inputs the assembled outputs of the syntactic component and, as a result of the very syntactic structure imposed by the syntax are then able to assign their sound and meaning interpretations. If this is an accurate characterization, Chomsky's long-standing postulation of mental organs, and I will argue, the advancement of new hypotheses concerning physiological inter-organ functions, has attained in current biolinguistic Minimalist method a significant unification with foundational aspects of physiological explanation in other areas of biology. (shrink)

Many of the formalisms used in Attribute Value grammar are notational variants of languages of propositional modal logic, and testing whether two Attribute Value Structures unify amounts to testing for modal satisfiability. In this paper we put this observation to work. We study the complexity of the satisfiability problem for nine modal languages which mirror different aspects of AVS description formalisms, including the ability to express re-entrancy, the ability to express generalisations, and the ability to express recursive constraints. Two (...) main techniques are used: either Kripke models with desirable properties are constructed, or modalities are used to simulate fragments of Propositional Dynamic Logic. Further possibilities for the application of modal logic in computational linguistics are noted. (shrink)

A two-stage procedure is described which induces type-logical grammar lexicons from sentences annotated with skeletal terms of the simply typed lambda calculus. First, a generalized formulae-as-types correspondence is exploited to obtain all the type-logical proofs of the sample sentences from their lambda terms. The resulting lexicons are then optimally unified. The first stage constitutes the semantic bootstrapping (Pinker, Language Learnability and Language Development, Harvard University Press, 1984), while the unification procedure of Buszkowski and Penn represents a first attempt at (...) structure-dependent distributional learning of the syntactic and semantic categories. This effort extends earlier induction procedures (Buszkowski and Penn, 1990, Studia Logica 49, 431–454; Kanazawa, 1998, CSLI Publications and the European Association for Logic, Language and Information) for classical categorial grammar to at first the non-associative Lambek calculus, and then to a large class of type logics enriched by modal operators and structural rules. (shrink)

A two-stage procedure is described which induces type-logical grammar lexicons from sentences annotated with skeletal terms of the simply typed lambda calculus. First, a generalized formulae-as-types correspondence is exploited to obtain all the type-logical proofs of the sample sentences from their lambda terms. The resulting lexicons are then optimally unified. The first stage constitutes the semantic bootstrapping (Pinker, Language Learnability and Language Development, Harvard University Press, 1984), while the unification procedure of Buszkowski and Penn represents a first attempt at (...) structure-dependent distributional learning of the syntactic and semantic categories. This effort extends earlier induction procedures (Buszkowski and Penn, 1990, Studia Logica 49, 431–454; Kanazawa, 1998, CSLI Publications and the European Association for Logic, Language and Information) for classical categorial grammar to at first the non-associative Lambek calculus, and then to a large class of type logics enriched by modal operators and structural rules. (shrink)

The concept of love has emerged as a central topic for philosophical and theoretical discussion over the past few years. Whereas the dominant ideology of love in contemporary culture insists that love be understood as a discovery of my long lost second half with whom I merge and finally recreate a whole, contemporary philosophers and theorists have stressed the need to reconsider the concept of love within an ethical framework that can sustain the idea of the other as forever different (...) and separate. Taking as a starting point two different taxi scenes offered by Foucault and Woolf respectively, the article outlines and discusses those two contemporary love grammars, focusing on the concepts of lack and fantasy. Whereas Woolf’s taxi scene is reminiscent of a notion of love as a fantasy of unification, Foucault’s notion of love not only observes the need to maintain the other’s specificity and separateness, but also considers lack and fantasy to be primary and fundamental parts of love as lived experience. While Foucault insists on pleasure and action he also observes the central and unavoidable power of imagination that is attributed the name and function of recollection. The article finally addresses the question of if and how we might be responsible for our daydreams and fantasies. (shrink)

Feature logics are the logical basis for so-called unification grammars studied in computational linguistics. We investigate the expressivity of feature terms with negation and the functional uncertainty construct needed for the description of long-distance dependencies and obtain the following results: satisfiability of feature terms is undecidable, sort equations can be internalized, consistency of sort equations is decidable if there is at least one atom, and consistency of sort equations is undecidable if there is no atom.

An attractive way to model the relation between an underspecified syntactic representation and its completions is to let the underspecified representation correspond to a logical description and the completions to the models of that description. This approach, which underlies the Description Theory of Marcus et al. 1983 has been integrated in Vijay-Shanker 1992 with a pure unification approach to Lexicalized Tree-Adjoining Grammars (Joshi et al. 1975, Schabes 1990). We generalize Description Theory by integrating semantic information, that is, we propose to (...) tackle both syntactic and semantic underspecification using descriptions. (shrink)

This book introduces generative grammar as an area of study and asks what it tells us about the human mind. Wolfram Hinzen lays the foundation for the unification of modern generative linguistics with the philosophies of mind and language. He introduces Chomsky's program of a 'minimalist' syntax as a novel explanatory vision of the human mind. He explains how the Minimalist Program originated in work in cognitive science, biology, linguistics, and philosophy, and examines its implications for work in these (...) fields. He considers the way the human mind is designed when seen as an arrangement of structural patterns in nature, and argues that its design is the product not so much of adaptive evolutionary history as of principles and processes that are ahistorical and internalist in character. Linguistic meaning, he suggests, arises in the mind as a consequence of structures emerging on formal rather than functional grounds. From this he substantiates an unexpected and deeply unfashionable notion of human nature. Clearly written in nontechnical language and assuming a limited knowledge of the fields it examines and links, Minimal Mind Design will appeal to a wide range of scholars in linguistics, philosophy, and cognitive science. It also provides an exceptionally clear insight into the nature and aims of Chomsky's Minimalist Program. (shrink)

Cognitive Linguistics is an approach to language study based on three central premises: that the function of language is to convey meaning, that linguistic description must rely on constructs that are psychologically real, and that grammar emerges from usage. Over the last 40 years, this approach to studying language has made enormous strides in virtually every aspect of linguistic inquiry, achieving major insights as well as bringing about a conceptual unification of the language sciences. However, it has also faced (...) problems, which, I argue, must be addressed if the approach is to continue to flourish. Some of these are shared with generative linguistics, while some are peculiar to the cognitive approach. The former include excessive reliance on introspective evidence; paying only lip service to the Cognitive Commitment; too much focus on hypothesis formulation (and not enough on hypothesis testing); ignoring individual differences; and neglecting the social aspects of language. The latter include assuming that we can deduce mental representations from patterns of use and equating distribution with meaning. I conclude by sketching out how these pitfalls could be avoided. (shrink)

In the paper, various notions of the logical semiotic sense of linguistic expressions – namely, syntactic and semantic, intensional and extensional – are considered and formalised on the basis of a formal-logical conception of any language L characterised categorially in the spirit of certain Husserl's ideas of pure grammar, Leśniewski-Ajdukiewicz's theory of syntactic/semantic categories and, in accordance with Frege's ontological canons, Bocheński's and some of Suszko's ideas of language adequacy of expressions of L. The adequacy ensures their unambiguous syntactic (...) and semantic senses and mutual, syntactic and semantic correspondence guaranteed by the acceptance of a postulate of categorial compatibility of syntactic and semantic (extensional and intensional) categories of expressions of L. This postulate defines the unification of these three logical senses. There are three principles of compositionality which follow from this postulate: one syntactic and two semantic ones already known to Frege. They are treated as conditions of homomorphism of partial algebra of L into algebraic models of L: syntactic, intensional and extensional. In the paper, they are applied to some expressions with quantifiers. Language adequacy connected with the logical senses described in the logical conception of language L is, obviously, an idealisation. The syntactic and semantic unambiguity of its expressions is not, of course, a feature of natural languages, but every syntactically and semantically ambiguous expression of such languages may be treated as a schema representing all of its interpretations that are unambiguous expressions. (shrink)

Details concerning the original PATR-II system can be found in Shieber et al (1983). For an introduction to the linguistic applications of PATR-II and related grammar formalisms, see Shieber (1986). For a more general computational overview of unification, see I

No categories

Direct download (2 more)  

 

Export citation  

 

Bookmark  

Name der Zeitschrift: Cognitive Linguistics Jahrgang: 27 Heft: 4 Seiten: 465-477.

Typed feature structures are used extensively for the specification of linguistic information in many formalisms. The subsumption relation orders TFSs by their information content. We prove that subsumption of acyclic TFSs is well founded, whereas in the presence of cycles general TFS subsumption is not well founded. We show an application of this result for parsing, where the well-foundedness of subsumption is used to guarantee termination for grammars that are off-line parsable. We define a new version of off-line parsability that (...) is less strict than the existing one; thus termination is guaranteed for parsing with a larger set of grammars. (shrink)

This book constitutes the thoroughly refereed post-proceedings of the Third International Conference on Logical Aspects of Computational Linguistics, LACL'98, held in Grenoble, France, in December 1998. The 15 revised full papers presented together with one invited paper were carefully reviewed and selected during two rounds of refereeing from 33 submissions and 19 conference presentations. Among the topics covered are various types of grammars, categorical inference, automated reasoning, constraint handling, logical forms, dialogue semantics, unification, and proofs.

We show that the variety of Heyting algebras has finitary unification type. We also show that the subvariety obtained by adding it De Morgan law is the biggest variety of Heyting algebras having unitary unification type. Proofs make essential use of suitable characterizations (both from the semantic and the syntactic side) of finitely presented projective algebras.

In this paper, we defend a novel, multidimensional account of representational unification, which we distinguish from integration. The dimensions of unity are simplicity, generality and scope, non-monstrosity, and systematization. In our account, unification is a graded property. The account is used to investigate the issue of how research traditions contribute to representational unification, focusing on embodied cognition in cognitive science. Embodied cognition contributes to unification even if it fails to offer a grand unification of cognitive science. The study of this (...) failure shows that unification, contrary to what defenders of mechanistic explanation claim, is an important mechanistic virtue of research traditions. (shrink)

Predictive processing (PP) has been repeatedly presented as a unificatory account of perception, action, and cognition. In this paper, we argue that this is premature: As a unifying theory, PP fails to deliver general, simple, homogeneous, and systematic explanations. By examining its current trajectory of development, we conclude that PP remains only loosely connected both to its computational framework and to its hypothetical biological underpinnings, which makes its fundamentals unclear. Instead of offering explanations that refer to the same set of (...) principles, we observe systematic equivocations in PP‐based models, or outright contradictions with its avowed principles. To make matters worse, PP‐based models are seldom empirically validated, and they are frequently offered as mere just‐so stories. The large number of PP‐based models is thus not evidence of theoretical progress in unifying perception, action, and cognition. On the contrary, we maintain that the gap between theory and its biological and computational bases contributes to the arrested development of PP as a unificatory theory. Thus, we urge the defenders of PP to focus on its critical problems instead of offering mere re‐descriptions of known phenomena, and to validate their models against possible alternative explanations that stem from different theoretical assumptions. Otherwise, PP will ultimately fail as a unified theory of cognition. (shrink)

i How can one talk about 'understanding' and 'not understanding' a proposition? Surely it is not a proposition until it's understood ? ...

The official model of explanation proposed by the logical empiricists, the covering law model, is subject to familiar objections. The goal of the present paper is to explore an unofficial view of explanation which logical empiricists have sometimes suggested, the view of explanation as unification. I try to show that this view can be developed so as to provide insight into major episodes in the history of science, and that it can overcome some of the most serious difficulties besetting the (...) covering law model. (shrink)

Explanatory unification—the urge to “explain much by little”—serves as an ideal of theorizing not only in natural sciences but also in the social sciences, most notably in economics. The ideal is occasionally challenged by appealing to the complexity and diversity of social systems and processes in space and time. This article proposes to accommodate such doubts by making a distinction between two kinds of unification and suggesting that while such doubts may be justified in regard to mere derivational unification (which (...) serves as a formal constraint on theories), it is less justified in the case of ontological unification (which is a result of factual discovery of the actual degree of underlying unity in the world). (shrink)