Handbook of Weighted Automata / Edition 1

Hardcover (Print)
Buy New
Buy New from BN.com
$154.39
Used and New from Other Sellers
Used and New from Other Sellers
from $146.95
Usually ships in 1-2 business days
(Save 35%)
Other sellers (Hardcover)
  • All (5) from $146.95   
  • New (4) from $146.95   
  • Used (1) from $252.17   

Overview

Weighted finite automata are classical nondeterministic finite automata in which the transitions carry weights. These weights may model, for example, the cost involved when executing a transition, the resources of time needed for this, or the probability or reliability of its successful execution. Weights can also be added to classical automata with infinite state sets like pushdown automata, and this extension constitutes the general concept of weighted automata. Since their introduction in the 1960s they have stimulated research in related areas of theoretical computer science, including formal language theory, algebra, logic, and discrete structures. Moreover, weighted automata and weighted context-free grammars have found application in natural-language processing, speech recognition, and digital image compression.

This book covers all the main aspects of weighted automata and formal power series methods, ranging from theory to applications. The contributors are the leading experts in their respective areas, and each chapter presents a detailed survey of the state of the art and pointers to future research. The chapters in Part I cover the foundations of the theory of weighted automata, specifically addressing semirings, power series, and fixed point theory. Part II investigates different concepts of weighted recognizability. Part III examines alternative types of weighted automata and various discrete structures other than words. Finally, Part IV deals with applications of weighted automata, including digital image compression, fuzzy languages, model checking, and natural-language processing.

Computer scientists and mathematicians will find this book and excellent surveyand reference volume, and it will also be a valuable resource for students exploring this exciting research area.

Read More Show Less

Editorial Reviews

From the Publisher

From the reviews:

"This book is an excellent reference for researchers in the field, as well as students interested in this research area. The presentation of applications makes it interesting to researchers from other fields to study weighted automata. ... One of the main arguments in favor of this handbook is the completeness of its index table — usually a faulty section in such volumes. The chapters are globally well-written and self-contained, thus pleasant to read, and the efforts put to maintain consistency in vocabulary thorough the book are very appreciable." (Michaël Cadilhac, The Book Review Column 43-3, 2012)

“The book presents a broad survey, theory and applications, of weighted automata, classical nondeterministic automata in which transitions carry weights. … The individual articles are written by well-known researchers in the field: they include extensive lists of references and many open problems. The book is valuable for both computer scientists and mathematicians (being interested in discrete structures).” (Cristian S. Calude, Zentralblatt MATH, Vol. 1200, 2011)

Read More Show Less

Product Details

Table of Contents

Part I Foundations

Chapter 1 Semirings and Formal Power Series Manfred Droste Werner Kuich 3

1 Introduction 3

2 Monoids and Semirings 5

3 Formal Power Series 12

4 Matrices 17

5 Cycle-Free Linear Equations 22

References 26

Chapter 2 Fixed Point Theory Zoltán Ésik 29

1 Introduction 29

2 Least Fixed Points 30

3 Conway Theories 38

4 Iteration Theories 41

5 Unique Fixed Points 44

6 Fixed Points of Linear Functions 46

6.1 Inductive *-Semirings 51

6.2 Complete Semirings 52

6.3 Iterative Semirings 53

7 Fixed Points of Affine Functions 54

7.1 Complete Semiring-Semimodule Pairs 59

7.2 Bi-inductive Semiring-Semimodule Pairs 61

References 62

Part II Concepts of Weighted Recognizability

Chapter 3 Finite Automata Zoltán Ésik Werner Kuich 69

1 Introduction 69

2 Finite Automata over Semirings 70

2.1 Finite Automata over Arbitrary Power Series Semirings 72

2.2 Finite Automata over Conway Semirings 75

2.3 Finite Linear Systems 81

3 Finite Automata over Quemirings 83

3.1 Semiring-Semimodule Pairs and Quemirings 85

3.2 Finite Automata over Quemirings and a Kleene Theorem 91

3.3 Finite Linear Systems over Quemirings 99

References 103

Chapter 4 Rational and Recognisable Power Series Jacques Sakarovitch 105

1 Introduction 106

2 Rational Series and Weighted Rational Expressions 107

2.1 Series over a Graded Monoid 107

2.2 Rational Series 114

3 Weighted Automata 122

3.1 The Behaviour of a Weighted Automaton 122

3.2 The Fundamental Theorem of Automata 126

3.3 Conjugacy and Covering of Automata 132

4 Recognisable Series and Representations 138

4.1 The Family of Recognisable Series 138

4.2 OtherProducts on Recognisable Series 141

4.3 Series on a Product of Monoids 145

5 Series over a Free Monoid 151

5.1 The Representability Theorem 152

5.2 Reduced Representations 157

5.3 Applications of the Reduction of Representations 161

6 Support of Rational Series 165

7 Notes 168

7.1 General Sources 168

7.2 Notes to Sect. 2: Rational Series 169

7.3 Notes to Sect. 3: Weighted Automata 169

7.4 Notes to Sect. 4: Recognisable Series 170

7.5 Notes to Sect. 5: Series over a Free Monoid 170

7.6 Notes to Sect. 6: Support of Rational Series 171

References 171

Chapter 5 Weighted Automata and Weighted Logics Manfred Droste Paul Gastin 175

1 Introduction 175

2 MSO-Logic and Weighted Automata 178

3 Weighted Logics 181

4 Unambiguous Formulas 185

5 Definability Equals Recognizability 189

6 Locally Finite Semirings 194

7 Weighted Automata on Infinite Words 197

8 Weighted Logics on Infinite Words 203

9 Conclusions and Open Problems 206

References 208

Chapter 6 Weighted Automata Algorithms Mehryar Mohri 213

1 Introduction 214

2 Preliminaries 214

2.1 Semirings 214

2.2 Weighted Transducers and Automata 215

3 Shortest-Distance Algorithms 217

3.1 All-Pairs Shortest-Distance Problems 218

3.2 Single-Source Shortest-Distance Problems 222

4 Rational Operations 223

5 Elementary Unary Operations 226

6 Fundamental Binary Operations 226

6.1 Composition 226

6.2 Intersection 231

6.3 Difference 231

7 Optimization Algorithms 233

7.1 Epsilon-Removal 233

7.2 Determinization 237

7.3 Weight Pushing 241

7.4 Minimization 243

7.5 Synchronization 246

8 Conclusion 250

References 250

Part III Weighted Discrete Structures

Chapter 7 Algebraic Systems and Pushdown Automata Ion Petre Arto Salomaa 257

1 Introduction 257

2 Auxiliar Notions and Results 258

3 Algebraic Power Series 261

3.1 Definition and Basic Reductions 261

3.2 Interconnections with Context-Free Grammars 265

3.3 Normal Forms 267

3.4 Theorems of Shamir and Chomsky-Schützenberger 271

4 Transductions 275

5 Pushdown Automata 279

5.1 Pushdown Transition Matrices 279

5.2 S"∑*"-Pushdown Automata 281

5.3 Equivalence with Algebraic Systems 284

6 Other Topics 287

References 288

Chapter 8 Lindenmayer Systems Juha Honkala 291

1 Introduction 291

2 Iterated Morphisms and Rational Series 292

3 Lindenmayerian Algebraic Series 296

4 DOL Power Series 302

5 Other Power Series Generalizations of L Systems 307

References 309

Chapter 9 Weighted Tree Automata and Tree Transducers Zoltán Fülöp Heiko Vogler 313

1 Introduction 314

2 Preliminaries 316

2.1 General Notation 316

2.2 Trees 316

2.3 Algebraic Concepts 317

2.4 Tree Series 320

3 Weighted Tree Automata 320

3.1 Bottom-up Tree Automata 320

3.2 Recognizable Tree Series 321

3.3 Closure Properties 326

3.4 Support of Recognizable Tree Series 328

3.5 Determinization of Weighted Tree Automata 330

3.6 Pumping Lemmata and Decidability 331

3.7 Finite Algebraic Characterizations of Recognizable Tree Series 335

3.8 Equational Tree Series 342

3.9 Rational Tree Series 347

3.10 MSO-Defmable Tree Series 349

3.11 Other Models Related to Recognizable Tree Series 353

3.12 Further Results 360

4 IO-Substitution and Tree Series Transformations 361

5 Weighted Tree Transducers 364

5.1 Tree Transdumers 364

5.2 The Basic Model 365

5.3 Restricted Models 370

5.4 Composition and Decomposition 374

5.5 The Inclusion Diagram of Some Fundamental wtt Classes 386

5.6 Hierarchies 388

5.7 Further Models of Weighted Tree Transducers 391

5.8 Further Results 394

References 394

Chapter 10 Traces, Series-Parallel Posets, and Pictures: A Weighted Study Ina Fichtner Dietrich Kuske Ingmar Meinecke 405

1 Introduction 406

2 Traces 407

2.1 Weighted Distributed Systems 407

2.2 Other Formalisms: Presentations, Expressions, and Logics 411

2.3 Relating the Formalisms 413

2.4 History and Overview 421

3 Series-Parallel Posets 423

3.1 Series-Parallel Posets and Bisemirings 423

3.2 Weighted Branching Automata 425

3.3 Rationality 427

3.4 The Hadamard Product 433

3.5 History and Overview 435

4 Pictures 436

4.1 Pictures and Weighted Picture Automata 436

4.2 Other Formalisms: Expressions and Logics 438

4.3 Relating the Formalisms 440

4.4 Decidability Issues 444

4.5 History and Overview 445

References 446

Part IV Applications

Chapter 11 Digital Image Compression Jürgen Albert Jarkko Karl 453

1 Introduction 453

2 Image Types 454

3 Weighted Finite Automata and Multi-resolution Images 457

4 Drawing WFA Images 459

5 An Encoding Algorithm 460

6 Practical Image Compression Using WFA 463

7 Weighted Finite Transducers (WFT) 469

8 Parametric Weighted Finite Automata (PWFA) 472

9 Conclusions and Open Problems 476

References 477

Chapter 12 Fuzzy Languages George Rahonis 481

1 Introduction 481

2 Lattices and Fuzzy Languages 483

3 Fuzzy Recognizability over Bounded Distributive Lattices 486

3.1 Fuzzy Recognizability over Finite Words 487

3.2 Fuzzy Recognizability over Infinite Words 495

3.3 Multi-valued MSO Logic 500

4 Fuzzy Languages: An Overview 505

4.1 Fuzzy Languages over l-Monoids 506

4.2 Fuzzy Languages over Residuated Lattices 507

4.3 Fuzzy Automata with Outputs 509

4.4 Fuzzy Abstract Families of Languages 509

4.5 Fuzzy Tree Languages 509

5 Applications 510

References 513

Chapter 13 Model Checking Linear-Time Properties of Probabilistic Systems Christel Baier Marcus Grö$er Frank Ciesinski 519

1 Introduction 519

2 Markov Decision Processes 526

3 Maximal Reachability Probabilities 533

4 Model Checking w-Regular Properties 538

5 Partial Order Reduction 547

6 Partially Observable MDPs 557

7 Conclusion 559

8 Appendix 560

References 563

Chapter 14 Applications of Weighted Automata in Natural Language Processing Kevin Knight Jonathan May 571

1 Background 571

2 WFST Techniques for Natural Language Processing 572

2.1 Example 1: Transliteration 573

2.2 Example 2: Translation 578

2.3 Language Modeling 582

3 Applications of Weighted String Automata 583

3.1 Language Translation 584

3.2 Speech Recognition 584

3.3 Lexical Processing 585

3.4 Tagging 585

3.5 Summarization 586

3.6 Optical Character Recognition 586

4 Applications of Weighted Tree Automata 586

4.1 Open Problems 590

5 Conclusion 591

References 591

Index 597

Read More Show Less

Customer Reviews

Be the first to write a review
( 0 )
Rating Distribution

5 Star

(0)

4 Star

(0)

3 Star

(0)

2 Star

(0)

1 Star

(0)

Your Rating:

Your Name: Create a Pen Name or

Barnes & Noble.com Review Rules

Our reader reviews allow you to share your comments on titles you liked, or didn't, with others. By submitting an online review, you are representing to Barnes & Noble.com that all information contained in your review is original and accurate in all respects, and that the submission of such content by you and the posting of such content by Barnes & Noble.com does not and will not violate the rights of any third party. Please follow the rules below to help ensure that your review can be posted.

Reviews by Our Customers Under the Age of 13

We highly value and respect everyone's opinion concerning the titles we offer. However, we cannot allow persons under the age of 13 to have accounts at BN.com or to post customer reviews. Please see our Terms of Use for more details.

What to exclude from your review:

Please do not write about reviews, commentary, or information posted on the product page. If you see any errors in the information on the product page, please send us an email.

Reviews should not contain any of the following:

  • - HTML tags, profanity, obscenities, vulgarities, or comments that defame anyone
  • - Time-sensitive information such as tour dates, signings, lectures, etc.
  • - Single-word reviews. Other people will read your review to discover why you liked or didn't like the title. Be descriptive.
  • - Comments focusing on the author or that may ruin the ending for others
  • - Phone numbers, addresses, URLs
  • - Pricing and availability information or alternative ordering information
  • - Advertisements or commercial solicitation

Reminder:

  • - By submitting a review, you grant to Barnes & Noble.com and its sublicensees the royalty-free, perpetual, irrevocable right and license to use the review in accordance with the Barnes & Noble.com Terms of Use.
  • - Barnes & Noble.com reserves the right not to post any review -- particularly those that do not follow the terms and conditions of these Rules. Barnes & Noble.com also reserves the right to remove any review at any time without notice.
  • - See Terms of Use for other conditions and disclaimers.
Search for Products You'd Like to Recommend

Recommend other products that relate to your review. Just search for them below and share!

Create a Pen Name

Your Pen Name is your unique identity on BN.com. It will appear on the reviews you write and other website activities. Your Pen Name cannot be edited, changed or deleted once submitted.

 
Your Pen Name can be any combination of alphanumeric characters (plus - and _), and must be at least two characters long.

Continue Anonymously

    If you find inappropriate content, please report it to Barnes & Noble
    Why is this product inappropriate?
    Comments (optional)