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 or 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 an excellent survey and reference volume, and it will also be a valuable resource for students exploring this exciting research area.

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 or 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 an excellent survey and reference volume, and it will also be a valuable resource for students exploring this exciting research area.

This Festschrift volume, published in honor of Symeon Bozapalidis on the occasion of his retirement after more than 35 years of teaching activity, focuses on the subjects taught by Symeon, namely: algebra, linear algebra, mathematical logic, number theory, automata theory, tree languages and series, algebraic semantics, and fuzzy languages. Since 1982 -- at the Aristotle University of Thessaloniki -- Symeon's main interests have been closely connected with the algebraic foundations in computer science. In particular, he contributed to the development of the theory of tree languages and series, the axiomatization of graphs, picture theory, and fuzzy languages. The volume contains 15 invited papers, written by colleagues, friends, and students of Symeon. All of the papers were carefully refereed and are connected to his research topics. Most of the papers were presented at the Workshop on Algebraic Foundations in Computer Science, held in Thessaloniki, Greece, during November 7--8, 2011.

This book constitutes the thoroughly refereed post-proceedings of the 5th International Conference on Developments in Language Theory, DLT 2001, held in Vienna, Austria, in July 2001.The 24 revised full papers presented together with 10 revised invited papers were carefully selected during two rounds of reviewing and revision from a total of 64 papers submitted. Among the topics covered are grammars and acceptors, efficient algorithms for languages, combinatorial and algebraic properties, decision problems, relations to complexity theory, logic, picture description and analysis, DNA computing, cryptography, and concurrency.

This volume presents the proceedings of the 19th International Colloquium onAutomata, Languages, and Programming (ICALP 92) in a series of meetings sponsored by the European Association for Theoretical Computer Science (EATCS). ICALP is a broadly based conference covering all aspects of theoretical computer science, including such topics as computability, automata, formal languages, term rewriting, analysis of algorithms, computational geometry, computational complexity, symbolic and algebraic computation, cryptography, data types and data structures, theory of databases and knowledge bases, semantics of programming languages, program specification, transformation and verification, foundations of logic programming, theory of logical design andlayout, parallel and distributed computation, theory of concurrency, and theory of robotics. The papers in the volume are grouped into thematic parts corresponding to their order of presentation at ICALP 92.