Theoretical Studies in Computer Science (eBook)

Jeffrey D. Ullman (Herausgeber)

eBook Download: PDF

2014 | 1. Auflage
350 Seiten
Elsevier Science (Verlag)
978-1-4832-6754-8 (ISBN)

Infos

Theoretical Studies in Computer Science focuses on the field of theoretical computer science. This book discusses the context-free multi-languages, non-membership in certain families of context-free languages, and single tree grammars. The complexity of structural containment and equivalence, interface between language theory and database theory, and automata theory for database theoreticians are also deliberated. This text likewise covers the datalog linearization of chain queries, expressive power of query languages, and object identity and query equivalences. Other topics include the unified approach to data and meta-data modification for data/knowledge bases, polygon clipping algorithms, and convex polygon generator. This publication is intended for computer scientists and researchers interested in theoretical computer science.

Inhalt

Front Cover 1
Theoretical Studies in Computer Science 4
Copyright Page 5
Table of Contents 6
Contributors 8
Preface and Dedication 10
Chapter 1. Context-Free Multilanguages 12
1. Multisets 13
Multilanguages 15
Transformations 16
Transduction 21
Quantitative considerations 23
Conclusions 23
References 24
Chapter 2. Proving Nonmembership in Certain Families of Context Free Languages 26
Abstract 26
1 
26 
2 Technical Background 27
3 The Classical Results 29
4 Deterministic Languages 32
5 A Hierarchy Result 44
6 The LL Languages 51
7 Simple Languages 64
8 Precedence Languages 74
9 Conclusion 79
References 79
Chapter 3. Single Tree Grammars 84
Abstract 84
1 Introduction 85
2 Intercalation Lemma and Closure Properties 86
3 Recognition 89
4 Undecidable Properties of STL's 90
5 Relationship with 
98 
6 Applications 107
7 Conclusions 108
References 109
Chapter 4. The Complexity of Structural Containment and Equivalence 112
Abstract 112
1 Introduction 112
2 Notions of Grammar Similarity 115
3 Structural Containment for General Context-Free Grammars 118
4 Efficient Algorithm for Structural Containment by LL(k) Grammars 125
5 Efficient Algorithm for Structural Containment by Bounded Right Context Grammars 129
6 Conclusions 139
References 141
Chapter 5. The Interface Between Language Theory and Database Theory 144
ABSTRACT 144
1. INTRODUCTION 144
2. PROOF TREES AND PARSE TREES 149
3. EQUIVALENCE 
153 
4. DECISION THEOREMS 154
5. PARALLELIZATION OF LOGICAL QUERIES 157
6. FACTORING LOGIC PROGRAMS 159
7. REFERENCES 161
Chapter 6. Automata Theory for Database Theoreticians 164
Abstract 164
1 Introduction 164
2 A General Decidability Result for Datalog Programs 165
3 Emptiness and Containment 169
4 Length, Height, and Tallness 177
5 Two-Way Automata 182
6 Concluding Remarks 187
References 187
Chapter 7. On Datalog Linearization of Chain Queries 192
Abstract 192
1 Introduction 192
2 Preliminaries 194
3 Nonterminal-Bounded Positive Programmed Languages 195
4 Addressable Linearization 200
5 Characterizations 209
6 Log Space and Linearizations 213
7 The Dyck-Set Chain Query 215
References 216
Chapter 8. Expressive Power of Query Languages 218
Abstract 218
1 Introduction 218
2 Relational Query Languages and Their Relative Expressiveness 221
3 Sizing Up Languages 240
4 The Impact of Order 246
5 Non-Determinism 250
6 Expressiveness Above 
254 
References 258
Chapter 9. Object Identity and Query Equivalence 264
Abstract 264
1 Introduction 265
2 Preliminaries 267
3 ILOG and Equivalence 270
4 Straightforward Results 274
5 Isolated OID Creation 275
References 294
Chapter 10. A Unified Approach to Data and Meta-data Modification for Data/Knowledge Bases 298
Abstract 298
1 Introduction 299
2 Model Description 301
3 A Unified Approach to Data and Metadata Modification 305
4 An Experimental Prototype 313
5 Conclusions 318
References 320
Appendix 323
Chapter 11. Polygon Clipping: Analysis and Experiences 326
Abstract 326
1 Polygon Clipping Algorithms 327
2 Analytical and Timing Results 331
3 Convex Polygon Generator 340
4 References 350

Produkt-Details

• Erscheint lt. Verlag: 10.5.2014
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Theorie / Studium
• Themenwelt: Mathematik / Informatik ► Mathematik
• Themenwelt: Technik
• ISBN-10: 1-4832-6754-7 / 1483267547
• ISBN-13: 978-1-4832-6754-8 / 9781483267548