Investigations in Logic, Language and Computation [PhD Thesis]

✍ Scribed by Henricus Marinus Franciscus Maria Aarts

Publisher: University of Amsterdam
Year: 1995
Tongue: English
Leaves: 133
Series: ILLC Dissertation Series DS-1995-19
Category: Library

No coin nor oath required. For personal study only.

✦ Table of Contents

I Grammar Formalisms 11
1 Introduction 13
1.1 Categorial Grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.2 Contextsensitive
Grammars . . . . . . . . . . . . . . . . . . . . . . . . . 16
2 The Nonassociative
Fragment of L 19
2.1 Categorial Grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 Recognition for Categorial Grammars Based on NL . . . . . . . . . . . . 25
3 The Second Order Fragment of L 29
3.1 Categorial Grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2 The System Aux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3 Cut Elimination in Aux . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.4 The System ApplComp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.5 The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.6 Proof of Correctness of the Algorithm . . . . . . . . . . . . . . . . . . . . 41
3.7 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4 Acyclic Contextsensitive
Grammars 45
4.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.1.1 Contextsensitive
Grammars . . . . . . . . . . . . . . . . . . . . . 46
4.1.2 Labeled Contextsensitive
Grammars . . . . . . . . . . . . . . . . 47
4.1.3 Acyclic Contextsensitive
Grammars . . . . . . . . . . . . . . . . . 47
4.1.4 Growing Contextsensitive
Grammars . . . . . . . . . . . . . . . . 48
4.2 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.3 Properties of Acyclic Contextsensitive
Grammars . . . . . . . . . . . . . 49
4.3.1 Generative Power of Acyclic CSG’s . . . . . . . . . . . . . . . . . . 49
4.3.2 Complexity of Acyclic CSG’s . . . . . . . . . . . . . . . . . . . . . . 51
4.4 Uniform Recognition for ACSG is NPcomplete
: . . . . . . . . . . . . . . 53
4.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

II Programming in Logic 59
5 Complexity of Prolog Programs 61
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.2 Other Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.3 Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.3.2 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.4 Space Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.5 Time Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.6 Wellmoded
and Nicely Moded Programs . . . . . . . . . . . . . . . . . . 79
5.7 A Lower Estimate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.8 A Small Recapitulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.9 Two Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.10 Metalogical
Predicates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.11 Further Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.12 Existing Implementations of Earley Interpreters . . . . . . . . . . . . . 90
6 Proof of the Time Complexity Result 91
6.1 A More Efficient Earley Interpreter . . . . . . . . . . . . . . . . . . . . . 91
6.2 Complexity of the Earley interpreter . . . . . . . . . . . . . . . . . . . . . 97
6.3 Improved Earley Deduction . . . . . . . . . . . . . . . . . . . . . . . . . . 100
7 Fragments of L in Prolog 103
7.1 Nonassociative
Lambek Grammar . . . . . . . . . . . . . . . . . . . . . . 103
7.1.1 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
7.1.2 Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 104
7.2 Second Order Lambek Grammar . . . . . . . . . . . . . . . . . . . . . . . 106
7.2.1 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
7.2.2 Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 109
A An Implementation of the Earley Interpreter in Prolog 113
B A Reduction of 3SAT
to ACSG Recognition 119
B.1 The Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
B.2 A Derivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
Bibliography 123
Samenvatting 127
Summary 129
Curriculum Vitae 131

📜 SIMILAR VOLUMES

Resource Logics: Proof-theoretical Inves

📁 Resource Logics: Proof-theoretical Investigations [PhD Thesis]

✍ Dirk Roorda 📂 Library 📅 1991 🏛 University of Amsterdam 🌐 English

The KEY TOPIC OF this THESIS is the Lambek calculus. It is a logic on the one hand, and a grammar on the other. The system is studied in different disciplines, having their own interests. The logician asks for completeness and soundness, or more basically, for semantics itself; if he has a hang towa

Logics of Communication and Knowledge [P

📁 Logics of Communication and Knowledge [PhD Thesis]

✍ Floor Anna Gineke Sietsma 📂 Library 📅 2012 🏛 University of Amsterdam 🌐 English

Categorial Investigations: Logical and L

📁 Categorial Investigations: Logical and Linguistic Aspects of the Lambek Calculus [PhD Thesis]

✍ Michael Moortgat 📂 Library 📅 1988 🌐 English

This book grew out of my interest in different facets of categorial grammar, which covers a period of five years. The structure of the book shows traces of its derivational history. Chapters 3 and 2 are based in part on Moortgat (1988a) and (1988c). In the original papers the emphasis is on linguist

Modalities in Medieval Logic [PhD Thesis

📁 Modalities in Medieval Logic [PhD Thesis]

✍ Sara L. Uckelman 📂 Library 📅 2009 🏛 University of Amsterdam 🌐 English

Correspondence and Canonicity in Non-Cla

📁 Correspondence and Canonicity in Non-Classical Logic [PhD Thesis]

✍ Sumit Sourabh 📂 Library 📅 2015 🏛 University of Amsterdam 🌐 English

Algorithmic Correspondence and Completen

📁 Algorithmic Correspondence and Completeness in Modal Logic [PhD Thesis]

✍ Willem Ernst Conradie 📂 Library 📅 2006 🏛 University of the Witwatersrand 🌐 English

This thesis takes an algorithmic perspective on the correspondence between modal and hybrid logics on the one hand, and first-order logic on the other. The canonicity of formulae, and by implication the completeness of logics, is simultaneously treated. Modal formulae define second-order condit