Investigations in Logic, Language and Computation [PhD Thesis]

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