This book develops a formal theory of dependency structures and shows how combining them with a regular means of composition yields copious hierarchies of ever more powerful dependency languages. It also classifies several relevant grammatical formalisms.

Since 2002, FoLLI has awarded an annual prize for outstanding dissertations in the fields of Logic, Language and Information. This book is based on the PhD thesis of Marco Kuhlmann, joint winner of the E.W. Beth dissertation award in 2008. Kuhlmann’s thesis lays new theoretical foundations for the study of non-projective dependency grammars. These grammars are becoming increasingly important for approaches to statistical parsing in computational linguistics that deal with free word order and long-distance dependencies. The author provides new formal tools to define and understand dependency grammars, presents two new dependency language hierarchies with polynomial parsing algorithms, establishes the practical significance of these hierarchies through corpus studies, and links his work to the phrase-structure grammar tradition through an equivalence result with tree-adjoining grammars. The work bridges the gaps between linguistics and theoretical computer science, between theoretical and empirical approaches in computational linguistics, and between previously disconnected strands of formal language research.

Since 2002, FoLLI has awarded an annual prize for outstanding dissertations in the fields of Logic, Language and Information. This book is based on the PhD thesis of Marco Kuhlmann, joint winner of the E.W. Beth dissertation award in 2008. Kuhlmann's thesis lays new theoretical foundations for the study of non-projective dependency grammars. These grammars are becoming increasingly important for approaches to statistical parsing in computational linguistics that deal with free word order and long-distance dependencies. The author provides new formal tools to define and understand dependency grammars, presents two new dependency language hierarchies with polynomial parsing algorithms, establishes the practical significance of these hierarchies through corpus studies, and links his work to the phrase-structure grammar tradition through an equivalence result with tree-adjoining grammars. The work bridges the gaps between linguistics and theoretical computer science, between theoretical and empirical approaches in computational linguistics, and between previously disconnected strands of formal language research.

This book explores the adaptation of cognitive processes to limited resources. It deals with resource-bounded and resource-adaptive cognitive processes in human information processing and human-machine systems plus the related technology transfer issues.

Lexical Functional Grammar (LFG) is a nontransformational theory of linguistic structure, first developed in the 1970s by Joan Bresnan and Ronald M. Kaplan, which assumes that language is best described and modeled by parallel structures representing different facets of linguistic organization and information, related by means of functional correspondences. This volume has five parts. Part I, Overview and Introduction, provides an introduction to core syntactic concepts and representations. Part II, Grammatical Phenomena, reviews LFG work on a range of grammatical phenomena or constructions. Part III, Grammatical modules and interfaces, provides an overview of LFG work on semantics, argument structure, prosody, information structure, and morphology. Part IV, Linguistic disciplines, reviews LFG work in the disciplines of historical linguistics, learnability, psycholinguistics, and second language learning. Part V, Formal and computational issues and applications, provides an overview of computational and formal properties of the theory, implementations, and computational work on parsing, translation, grammar induction, and treebanks. Part VI, Language families and regions, reviews LFG work on languages spoken in particular geographical areas or in particular language families. The final section, Comparing LFG with other linguistic theories, discusses LFG work in relation to other theoretical approaches.

This volume provides a selection of the papers which were presented at the eleventh conference on Computational Linguistics in the Netherlands (Tilburg, 2000). It gives an accurate and up-to-date picture of the lively scene of computational linguistics in the Netherlands and Flanders. The volume covers the whole range from theoretical to applied research and development, and is hence of interest to both academia and industry. The target audience consists of students and scholars of computational linguistics, and speech and language processing (Linguistics, Computer Science, Electrical Engineering).

This volume provides a selection of the papers which were presented at the eleventh conference on Computational Linguistics in the Netherlands (Tilburg, 2000). It gives an accurate and up-to-date picture of the lively scene of computational linguistics in the Netherlands and Flanders. The volume covers the whole range from theoretical to applied research and development, and is hence of interest to both academia and industry. The target audience consists of students and scholars of computational linguistics, and speech and language processing (Linguistics, Computer Science, Electrical Engineering).

This book constitutes the refereed proceedings of the 14th International Conference on Formal Grammar 2009, held in Bordeaux, France, in July 2009. The 13 revised full papers presented, including two invited talks, were carefully reviewed and selected from 26 submissions. These articles in this book give an overview of new and original research on formal grammar, mathematical linguistics and the application of formal and mathematical methods to the study of natural language.

Given that context-free grammars (CFG) cannot adequately describe natural languages, grammar formalisms beyond CFG that are still computationally tractable are of central interest for computational linguists. This book provides an extensive overview of the formal language landscape between CFG and PTIME, moving from Tree Adjoining Grammars to Multiple Context-Free Grammars and then to Range Concatenation Grammars while explaining available parsing techniques for these formalisms. Although familiarity with the basic notions of parsing and formal languages is helpful when reading this book, it is not a strict requirement. The presentation is supported with many illustrations and examples relating to the different formalisms and algorithms, and chapter summaries, problems and solutions. The book will be useful for students and researchers in computational linguistics and in formal language theory.

There are not many people who can be said to have influenced and impressed researchers in so many disparate areas and language-geographic fields as Lauri Carlson, as is evidenced in the present Festschrift. His insight and acute linguistic sensitivity and linguistic rationality have spawned findings and research work in many areas, from non-standard etymology to hardcore formal linguistics, not forgetting computational areas such as parsing, terminological databases, and, last but not least, machine translation. In addition to his renowned and widely acknowledged insights in tense and aspect and its relationship with nominal quantification, and his ground-breaking work in dialog using game-theoretic machinery, Lauri has in the last fifteen years as Professor of Language Theory and Translation Technology contributed immensely to areas such as translation, terminology and general applications of computational linguistics. The three editors of the present volume have successfully performed doctoral studies under Lauri’s supervision, and wish with this volume to pay tribute to his supervision and to his influence in matters associated with research and scientific, linguistic and philosophical inquiry, as well as to his humanity and friendship.