1. 1 Descriptional Complexity --- An Introductory Survey, M. Kutrib 1
1.1. 1 Introduction 1
1.2. 1 Descriptional Systems and Complexity Measures 3
1.3. 1 Measuring Sizes 6
1.4. 1 Measuring Resources 33
1.5. 1 Non-Recursive Trade-Offs 39
1 References 51
2. 1 Classifying All Avoidable Sets of Partial Words of Size Two, E. Weissenstein 59
2.1. 1 Introduction 60
2.2. 1 Preliminaries 62
2.3. 1 Unavoidable Sets of Partial Words of Size Two 64
2.4. 1 Canonical Forms 70
2.5. 1 The Answer to the Conjectures 74
2.6. 1 The Classification 95
2.7. 1 Conclusion 99
1 References 100
3. 1 On Glushkov K-graphs, M. Flouret 103
3.1. 1 Introduction 103
3.2. 1 Definitions 105
3.3. 1 Acyclic Glushkov WFA Properties 114
3.4. 1 Glushkov K-graph with Orbits 124
3.5. 1 Algorithm for Orbit Reduction 127
3.6. 1 Conclusion 131
1 References 131
4. 1 Natural Language Dictionaries Implemented as Finite Automata, S. Ristov 133
4.1. 1 Dictionaries as Finite Automata 133
4.2. 1 Automata as Mappings 149
4.3. 1 Construction Methods 165
4.4. 1 Internal Structure and Compression 187
1 References 200
5. 1 Tree-Language Based Querying of Hierarchically Structured and Semi-Structured Data, A. Berlea 205
5.1. 1 Introduction 205
5.2. 1 Preliminaries 207
5.3. 1 Regular Forest Languages 217
5.4. 1 Grammar Queries 230
5.5. 1 Practical Application: A Pattern Language for XML Querying 259
5.6. 1 Online Querying 275
5.7. 1 Summary and Outlook 294
5.8. 1 Proofs of Theorems 295
1 References 306
6. 1 Quotient Monoids and Concurrent Behaviours, M. Koutny 313
6.1. 1 Introduction 314
6.2. 1 Preliminaries 318
6.3. 1 Partial Orders and Order Structures 326
6.4. 1 Mazurkiewicz Traces 334
6.5. 1 Comtraces 337
6.6. 1 Generalised Comtraces 354
6.7. 1 Elementary Net Systems 360
6.8. 1 EN-systems with Inhibitor and Mutex Arcs 372
6.9. 1 Concluding Remarks 382
1 References 383
7. 1 Correction Queries in Active Learning, C. Tirnauca 387
7.1. 1 Introduction 387
7.2. 1 Preliminaries 389
7.3. 1 Learning Models 391
7.4. 1 Learning with Correction Queries 393
7.5. 1 Polynomial Time Learning with Correction Queries 403
1 References 416
8. 1 Applications of Grammatical Inference in Software Engineering: Domain Specific Language Development, F. Javed 421
8.1. 1 Introduction 422
8.2. 1 Analysis Phase of DSL Development 424
8.3. 1 Design Phase of DSL Development 426
8.4. 1 Grammatical Inference and Language Design 429
8.5. 1 Case Study 445
8.6. 1 Related Work 448
8.7. 1 Conclusion 452
1 References 453
9. 1 Small Size Insertion and Deletion Systems, S. Verlan 459
9.1. 1 Introduction 459
9.2. 1 Definitions 461
9.3. 1 Basic Simulation Principles 466
9.4. 1 Insertion-Deletion Systems with Rules of Small Size 470
9.5. 1 Context-Free Insertion-Deletion Systems 472
9.6. 1 One-Sided Contextual Insertion-Deletion Systems 481
9.7. 1 Pure Insertion Systems 497
9.8. 1 Graph-Controlled Insertion-Deletion Systems 503
9.9. 1 Graph-Controlled Insertion-Deletion Systems with Priorities 514
9.10. 1 Bibliographical Remarks 520
1 References 521
10. 1 Accepting Networks of Evolutionary Word and Picture Processors: A Survey, V. Mitrana 525
10.1. 1 Introduction 525
10.2. 1 Basic Definitions 527
10.3. 1 Computational Power 536
10.4. 1 Universal ANEPs and ANEPFCs 541
10.5. 1 A Direct Simulation 544
10.6. 1 Accepting Networks of Splicing Processors 545
10.7. 1 Problem Solving with ANEPs/ANEPFCs 548
10.8. 1 Accepting Networks of Picture Processors 549
1 References 558
11. 1 Quantum Automata and Periodic Events, B. Palano 563
11.1. 1 Introduction 563
11.2. 1 Preliminaries 566
11.3. 1 Testing Periodicity on Unary Iqfa's 570
11.4. 1 Synthesis of Iqfa's Inducing Periodic Events 572
11.5. 1 Application to Periodic Languages 580
1 References 582
12. 1 Soliton Circuits and Network-Based Automata: Review and Perspectives, M. Kresz 585
12.1. 1 Introduction 586
12.2. 1 Basic Concepts 588
12.3. 1 Soliton Graphs and Automata 593
12.4. 1 Elementary Decomposition of Soliton Graphs and Automata 597
12.5. 1 Characterizing Soliton Automata 600
12.6. 1 Complete Systems of Soliton Automata 610
12.7. 1 Algorithms for Soliton Automata 615
12.8. 1 Extensions of the Model and Further Research 623
12.9. 1 Summary 627
1 References 628
13. 1 Inferring Leadership Structure from Data on a Syntax Change in English, W. Garrett Mitchener 633
13.1. 1 Introduction 634
13.2. 1 The Available Data 639
13.3. 1 Formulation of the Variable Influence Model 640
13.4. 1 Fitting the Do-support Data 644
13.5. 1 Results and Discussion 650
13.6. 1 Future Directions 652
13.7. 1 Conclusion 656
1 References 658
14. 1 Weighted Automata Modeling for High Density Linkage Disequilibrium Mapping, T. Trang 663
14.1. 1 Introduction 664
14.2. 1 Biological Problem and Formulation 667
14.3. 1 Fundamentals of Discrete Structures 676
14.4. 1 Variable Length Finite Automata (VLFA) 682
14.5. 1 Experimental Results on SNP Data 706
14.6. 1 Conclusion 719
1 References 720
1 Author Index 723
1 Subject Index