product iamge

Investigations in Logic, Language and Computation [PhD Thesis]

This document was uploaded by one of our users. The uploader already confirmed that they had the permission to publish it. If you are author/publisher or own the copyright of this documents, please report to us by using this DMCA report form.

Download
Search on Amazon

Simply click on the Download Book button.

Yes, Book downloads on Ebookily are 100% Free.

Sometimes the book is free on Amazon As well, so go ahead and hit "Search on Amazon"

Author(s): Henricus Marinus Franciscus Maria Aarts
Series: ILLC Dissertation Series DS-1995-19
Publisher: University of Amsterdam
Year: 1995

Language: English
Pages: 133
City: Amsterdam

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