Scientific Applications of Language Methods

Scientific Applications of Language Methods

by Carlos Martin-Vide
     
 

ISBN-10: 1848165447

ISBN-13: 9781848165441

Pub. Date: 11/03/2010

Publisher: Imperial College Press

Presenting interdisciplinary research at the forefront of present advances in information technologies and their foundations, Scientific Applications of Language Methods is a multi-author volume containing pieces of work (either original research or surveys) exemplifying the application of formal language tools in several fields, including logic and discrete

…  See more details below

Overview

Presenting interdisciplinary research at the forefront of present advances in information technologies and their foundations, Scientific Applications of Language Methods is a multi-author volume containing pieces of work (either original research or surveys) exemplifying the application of formal language tools in several fields, including logic and discrete mathematics, natural language processing, artificial intelligence, natural computing and bioinformatics.

Product Details

ISBN-13:
9781848165441
Publisher:
Imperial College Press
Publication date:
11/03/2010
Pages:
752
Product dimensions:
6.10(w) x 9.00(h) x 1.80(d)

Table of Contents

1 Descriptional Complexity-An Introductory Survey M. Holzer M. Kutrib 1

1.1 Introduction 1

1.2 Descriptional Systems and Complexity Measures 3

1.3 Measuring Sizes 6

1.4 Measuring Resources 33

1.5 Non-Recursive Trade-Offs 39

References 51

2 Classifying All Avoidable Sets of Partial Words of Size Two F. Blanchet-Sadri B. Blakeley J. Gunter S. Simmons E. Weissenstein 59

2.1 Introduction 60

2.2 Preliminaries 62

2.3 Unavoidable Sets of Partial Words of Size Two 64

2.4 Canonical Forms 70

2.5 The Answer to the Conjectures 74

2.6 The Classification 95

2.7 Conclusion 99

References 100

3 On Glushkov K-graphs P. Caron M. Flouret 103

3.1 Introduction 103

3.2 Definitions 105

3.3 Acyclic Glushkov WFA Properties 114

3.4 Glushkov K-graph with Orbits 124

3.5 Algorithm for Orbit Reduction 127

3.6 Conclusion 131

References 131

4 Natural Language Dictionaries Implemented as Finite Automata J. Daciuk J. Piskorski S. Ristov 133

4.1 Dictionaries as Finite Automata 133

4.2 Automata as Mappings 149

4.3 Construction Methods 165

4.4 Internal Structure and Compression 187

References 200

5 Tree-Language Based Querying of Hierarchically Structured and Semi-Structured Data A. Berlea 205

5.1 Introduction 205

5.2 Preliminaries 207

5.3 Regular Forest Languages 217

5.4 Grammar Queries 230

5.5 Practical Application: A Pattern Language for XML Querying 259

5.6 Online Querying 275

5.7 Summary and Outlook 294

5.8 Proofs of Theorems 295

References 306

6 Quotient Monoids and Concurrent Behaviours R. Janicki J. Kleijn M. Koutny 313

6.1 Introduction 314

6.2 Preliminaries 318

6.3 Partial Orders and Order Structures 326

6.4 Mazurkiewicz Traces 334

6.5 Comtraces 337

6.6 Generalised Comtraces 354

6.7 Elementary Net Systems 360

6.8 EN-systems with Inhibitor and Mutex Arcs 372

6.9 Concluding Remarks 382

References 383

7 Correction Queries in Active Learning C. Tîrnauca 387

7.1 Introduction 387

7.2 Preliminaries 389

7.3 Learning Models 391

7.4 Learning with Correction Queries 393

7.5 Polynomial Time Learning with Correction Queries 403

References 416

8 Applications of Grammatical Inference in Software Engineering: Domain Specific Language Development M. Mernik D. Hrncic B. R. Bryant F. Javed 421

8.1 Introduction 422

8.2 Analysis Phase of DSL Development 424

8.3 Design Phase of DSL Development 426

8.4 Grammatical Inference and Language Design 429

8.5 Case Study 445

8.6 Related Work 448

8.7 Conclusion 452

References 453

9 Small Size Insertion and Deletion Systems A. Alhazov A. Krassovitskiy Y. Rogozhin S. Verlan 459

9.1 Introduction 459

9.2 Definitions 461

9.3 Basic Simulation Principles 466

9.4 Insertion-Deletion Systems with Rules of Small Size 470

9.5 Context-Free Insertion-Deletion Systems 472

9.6 One-Sided Contextual Insertion-Deletion Systems 481

9.7 Pure Insertion Systems 497

9.8 Graph-Controlled Insertion-Deletion Systems 503

9.9 Graph-Controlled Insertion-Deletion Systems with Priorities 514

9.10 Bibliographical Remarks 520

References 521

10 Accepting Networks of Evolutionary Word and Picture Processors: A Survey F. Manea C. Martín-Vide V. Mitrana 525

10.1 Introduction 525

10.2 Basic Definitions 527

10.3 Computational Power 536

10.4 Universal ANEPs and ANEPFCs 541

10.5 A Direct Simulation 544

10.6 Accepting Networks of Splicing Processors 545

10.7 Problem Solving with ANEPs/ANEPFCs 548

10.8 Accepting Networks of Picture Processors 549

References 558

11 Quantum Automata and Periodic Events C. Mereghetti B. Palano 563

11.1 Introduction 563

11.2 Preliminaries 566

11.3 Testing Periodicity on Unary 1qfa's 570

11.4 Synthesis of 1qfa's Inducing Periodic Events 572

11.5 Application to Periodic Languages 580

References 582

12 Soliton Circuits and Network-Based Automata: Review and Perspectives M. Bartha M. Krész 585

12.1 Introduction 586

12.2 Basic Concepts 588

12.3 Soliton Graphs and Automata 593

12.4 Elementary Decomposition of Soliton Graphs and Automata 597

12.5 Characterizing Soliton Automata 600

12.6 Complete Systems of Soliton Automata 610

12.7 Algorithms for Soliton Automata 615

12.8 Extensions of the Model and Further Research 623

12.9 Summary 627

References 628

13 Inferring Leadership Structure from Data on a Syntax Change in English W. Garrett Mitchener 633

13.1 Introduction 634

13.2 The Available Data 639

13.3 Formulation of the Variable Influence Model 640

13.4 Fitting the Do-support Data 644

13.5 Results and Discussion 650

13.6 Future Directions 652

13.7 Conclusion 656

References 658

14 Weighted Automata Modeling for High Density Linkage Disequilibrium Mapping T. Trang 663

14.1 Introduction 664

14.2 Biological Problem and Formulation 667

14.3 Fundamentals of Discrete Structures 676

14.4 Variable Length Finite Automata (VLFA) 682

14.5 Experimental Results on SNP Data 706

14.6 Conclusion 719

References 720

Author Index 723

Subject Index 725

Read More

Customer Reviews

Average Review:

Write a Review

and post it to your social network

     

Most Helpful Customer Reviews

See all customer reviews >