Automata Theory and its Applications

Author: Bakhadyr Khoussainov,Anil Nerode

Publisher: Springer Science & Business Media

ISBN: 1461201713

Category: Mathematics

Page: 432

View: 8387

The theory of finite automata on finite stings, infinite strings, and trees has had a dis tinguished history. First, automata were introduced to represent idealized switching circuits augmented by unit delays. This was the period of Shannon, McCullouch and Pitts, and Howard Aiken, ending about 1950. Then in the 1950s there was the work of Kleene on representable events, of Myhill and Nerode on finite coset congruence relations on strings, of Rabin and Scott on power set automata. In the 1960s, there was the work of Btichi on automata on infinite strings and the second order theory of one successor, then Rabin's 1968 result on automata on infinite trees and the second order theory of two successors. The latter was a mystery until the introduction of forgetful determinacy games by Gurevich and Harrington in 1982. Each of these developments has successful and prospective applications in computer science. They should all be part of every computer scientist's toolbox. Suppose that we take a computer scientist's point of view. One can think of finite automata as the mathematical representation of programs that run us ing fixed finite resources. Then Btichi's SIS can be thought of as a theory of programs which run forever (like operating systems or banking systems) and are deterministic. Finally, Rabin's S2S is a theory of programs which run forever and are nondeterministic. Indeed many questions of verification can be decided in the decidable theories of these automata.

Automata, Logics, and Infinite Games

A Guide to Current Research

Author: Erich Grädel,Wolfgang Thomas,Thomas Wilke

Publisher: Springer

ISBN: 3540363874

Category: Computers

Page: 392

View: 1562

A central aim and ever-lasting dream of computer science is to put the development of hardware and software systems on a mathematical basis which is both firm and practical. Such a scientific foundation is needed especially for the construction of reactive programs, like communication protocols or control systems. For the construction and analysis of reactive systems an elegant and powerful theory has been developed based on automata theory, logical systems for the specification of nonterminating behavior, and infinite two-person games. The 19 chapters presented in this multi-author monograph give a consolidated overview of the research results achieved in the theory of automata, logics, and infinite games during the past 10 years. Special emphasis is placed on coherent style, complete coverage of all relevant topics, motivation, examples, justification of constructions, and exercises.

Cryptographic Applications of Analytic Number Theory

Complexity Lower Bounds and Pseudorandomness

Author: Igor Shparlinski

Publisher: Birkhäuser

ISBN: 3034880375

Category: Mathematics

Page: 414

View: 9600

The book introduces new techniques that imply rigorous lower bounds on the com plexity of some number-theoretic and cryptographic problems. It also establishes certain attractive pseudorandom properties of various cryptographic primitives. These methods and techniques are based on bounds of character sums and num bers of solutions of some polynomial equations over finite fields and residue rings. Other number theoretic techniques such as sieve methods and lattice reduction algorithms are used as well. The book also contains a number of open problems and proposals for further research. The emphasis is on obtaining unconditional rigorously proved statements. The bright side of this approach is that the results do not depend on any assumptions or conjectures. On the downside, the results are much weaker than those which are widely believed to be true. We obtain several lower bounds, exponential in terms of logp, on the degrees and orders of o polynomials; o algebraic functions; o Boolean functions; o linear recurrence sequences; coinciding with values of the discrete logarithm modulo a prime p at sufficiently many points (the number of points can be as small as pI/2+O:). These functions are considered over the residue ring modulo p and over the residue ring modulo an arbitrary divisor d of p - 1. The case of d = 2 is of special interest since it corresponds to the representation of the rightmost bit of the discrete logarithm and defines whether the argument is a quadratic residue.

Formal Languages, Automata and Numeration Systems 2

Applications to Recognizability and Decidability

Author: Michel Rigo

Publisher: John Wiley & Sons

ISBN: 1119042860

Category: Technology & Engineering

Page: 246

View: 6921

The interplay between words, computability, algebra andarithmetic has now proved its relevance and fruitfulness. Indeed,the cross-fertilization between formal logic and finite automata(such as that initiated by J.R. Büchi) or betweencombinatorics on words and number theory has paved the way torecent dramatic developments, for example, the transcendenceresults for the real numbers having a “simple” binaryexpansion, by B. Adamczewski and Y. Bugeaud. This book is at the heart of this interplay through a unifiedexposition. Objects are considered with a perspective that comesboth from theoretical computer science and mathematics. Theoreticalcomputer science offers here topics such as decision problems andrecognizability issues, whereas mathematics offers concepts such asdiscrete dynamical systems. The main goal is to give a quick access, for students andresearchers in mathematics or computer science, to actual researchtopics at the intersection between automata and formal languagetheory, number theory and combinatorics on words. The second of two volumes on this subject, this book coversregular languages, numeration systems, formal methods applied todecidability issues about infinite words and sets of numbers.

Formal Languages, Automata and Numeration Systems 1

Introduction to Combinatorics on Words

Author: Michel Rigo

Publisher: John Wiley & Sons

ISBN: 1119008220

Category: Computers

Page: 338

View: 6207

Formal Languages, Automaton and Numeration Systems presents readers with a review of research related to formal language theory, combinatorics on words or numeration systems, such as Words, DLT (Developments in Language Theory), ICALP, MFCS (Mathematical Foundation of Computer Science), Mons Theoretical Computer Science Days, Numeration, CANT (Combinatorics, Automata and Number Theory). Combinatorics on words deals with problems that can be stated in a non-commutative monoid, such as subword complexity of finite or infinite words, construction and properties of infinite words, unavoidable regularities or patterns. When considering some numeration systems, any integer can be represented as a finite word over an alphabet of digits. This simple observation leads to the study of the relationship between the arithmetical properties of the integers and the syntactical properties of the corresponding representations. One of the most profound results in this direction is given by the celebrated theorem by Cobham. Surprisingly, a recent extension of this result to complex numbers led to the famous Four Exponentials Conjecture. This is just one example of the fruitful relationship between formal language theory (including the theory of automata) and number theory.

Advances in Computer Science and its Applications

CSA 2013

Author: Hwa Young Jeong,Mohammad S. Obaidat,Neil Y. Yen,James J. (Jong Hyuk) Park

Publisher: Springer Science & Business Media

ISBN: 3642416748

Category: Mathematics

Page: 749

View: 6936

These proceedings focus on various aspects of computer science and its applications, thus providing an opportunity for academic and industry professionals to discuss the latest issues and progress in this and related areas. The book includes theory and applications alike.

Theoretical Advances and Applications of Fuzzy Logic and Soft Computing

Author: Oscar Castillo,Patricia Melin,Oscar Montiel Ross,Roberto Sepúlveda Cruz,Witold Pedrycz

Publisher: Springer Science & Business Media

ISBN: 3540724346

Category: Mathematics

Page: 626

View: 9550

This book comprises a selection of papers on theoretical advances and applications of fuzzy logic and soft computing from the IFSA 2007 World Congress, held in Cancun, Mexico, June 2007. These papers constitute an important contribution to the theory and applications of fuzzy logic and soft computing methodologies.

Advances in Temporal Logic

Author: Howard Barringer,Michael Fisher,Dov M. Gabbay,Graham Gough

Publisher: Springer Science & Business Media

ISBN: 9401595860

Category: Mathematics

Page: 453

View: 2042

Time is a fascinating subject and has long since captured mankind's imagination, from the ancients to modern man, both adult and child alike. It has been studied across a wide range of disciplines, from the natural sciences to philosophy and logic. Today, thirty plus years since Prior's work in laying out foundations for temporal logic, and two decades on from Pnueli's seminal work applying of temporal logic in specification and verification of computer programs, temporal logic has a strong and thriving international research community within the broad disciplines of computer science and artificial intelligence. Areas of activity include, but are certainly not restricted to: Pure Temporal Logic, e. g. temporal systems, proof theory, model theory, expressiveness and complexity issues, algebraic properties, application of game theory; Specification and Verification, e. g. of reactive systems, ofreal-time components, of user interaction, of hardware systems, techniques and tools for verification, execution and prototyping methods; Temporal Databases, e. g. temporal representation, temporal query ing, granularity of time, update mechanisms, active temporal data bases, hypothetical reasoning; Temporal Aspects in AI, e. g. modelling temporal phenomena, in terval temporal calculi, temporal nonmonotonicity, interaction of temporal reasoning with action/knowledge/belief logics, temporal planning; Tense and Aspect in Natural Language, e. g. models, ontologies, temporal quantifiers, connectives, prepositions, processing tempo ral statements; Temporal Theorem Proving, e. g. translation methods, clausal and non-clausal resolution, tableaux, automata-theoretic approaches, tools and practical systems.

Fuzzy Logic in Action: Applications in Epidemiology and Beyond

Author: Eduardo Massad,Neli Regina Siqueira Ortega,Laecio Carvalho de Barros,Claudio J. Struchiner

Publisher: Springer Science & Business Media

ISBN: 3540690921

Category: Medical

Page: 347

View: 2063

Fuzzy Logic in Action: Applications in Epidemiology and Beyond, co-authored by Eduardo Massad, Neli Ortega, Laécio Barros, and Cláudio Struchiner is a remarkable achievement. The book brings a major paradigm shift to medical sciences exploring the use of fuzzy sets in epidemiology and medical diagnosis arena. The volume addresses the most significant topics in the broad areas of epidemiology, mathematical modeling and uncertainty, embodying them within the framework of fuzzy set and dynamic systems theory. Written by leading contributors to the area of epidemiology, medical informatics and mathematics, the book combines a very lucid and authoritative exposition of the fundamentals of fuzzy sets with an insightful use of the fundamentals in the area of epidemiology and diagnosis. The content is clearly illustrated by numerous illustrative examples and several real world applications. Based on their profound knowledge of epidemiology and mathematical modeling, and on their keen understanding of the role played by uncertainty and fuzzy sets, the authors provide insights into the connections between biological phenomena and dynamic systems as a mean to predict, diagnose, and prescribe actions. An example is the use of Bellman-Zadeh fuzzy decision making approach to develop a vaccination strategy to manage measles epidemics in São Paulo. The book offers a comprehensive, systematic, fully updated and self- contained treatise of fuzzy sets in epidemiology and diagnosis. Its content covers material of vital interest to students, researchers and practitioners and is suitable both as a textbook and as a reference. The authors present new results of their own in most of the chapters. In doing so, they reflect the trend to view fuzzy sets, probability theory and statistics as an association of complementary and synergetic modeling methodologies.

Tree Automata and Languages

Author: M. Nivat,Andreas Podelski

Publisher: North-Holland


Category: Computers

Page: 485

View: 2240

The theory of tree languages, founded in the late Sixties and still active in the Seventies, was much less active during the Eighties. Now there is a simultaneous revival in several countries, with a number of significant results proved in the past five years. A large proportion of them appear in the present volume. The editors of this volume suggested that the authors should write comprehensive half-survey papers. This collection is therefore useful for everyone interested in the theory of tree languages as it covers most of the recent questions which are not treated in the very few rather old standard books on the subject. Trees appear naturally in many chapters of computer science and each new property is likely to result in improvement of some computational solution of a real problem in handling logical formulae, data structures, programming languages on systems, algorithms etc. The point of view adopted here is to put emphasis on the properties themselves and their rigorous mathematical exposition rather than on the many possible applications. This volume is a useful source of concepts and methods which may be applied successfully in many situations: its philosophy is very close to the whole philosophy of the ESPRIT Basic Research Actions and to that of the European Association for Theoretical Computer Science.

Handbook of Model Checking

Author: Edmund M. Clarke,Thomas A. Henzinger,Helmut Veith,Roderick Bloem

Publisher: Springer

ISBN: 3319105752

Category: Computers

Page: 1210

View: 4752

Model checking is a computer-assisted method for the analysis of dynamical systems that can be modeled by state-transition systems. Drawing from research traditions in mathematical logic, programming languages, hardware design, and theoretical computer science, model checking is now widely used for the verification of hardware and software in industry. The editors and authors of this handbook are among the world's leading researchers in this domain, and the 32 contributed chapters present a thorough view of the origin, theory, and application of model checking. In particular, the editors classify the advances in this domain and the chapters of the handbook in terms of two recurrent themes that have driven much of the research agenda: the algorithmic challenge, that is, designing model-checking algorithms that scale to real-life problems; and the modeling challenge, that is, extending the formalism beyond Kripke structures and temporal logic. The book will be valuable for researchers and graduate students engaged with the development of formal methods and verification tools.

Logik für Informatiker

Author: Uwe Schöning

Publisher: Spektrum Akademischer Verlag

ISBN: 9783827410054

Category: Computers

Page: 200

View: 6029

Das Buch macht den Leser mit den wesentlichen Teilgebieten der formalen Logik vertraut, die Bestandteil der Ausbildung in Theoretischer Informatik sind. Die Darstellung orientiert sich an den Bedürfnissen von Informatikstudierenden. Insbesondere werden viele mehr auf das Prinzipielle ausgerichtete Resultate der formalen Logik unter einem algorithmischen Gesichtspunkt behandelt. Diese Vorgehensweise erleichtert entscheidend den Zugang zu dem abstrakten Themengebiet. Prof. Schöning gelingt eine kompakte und verständliche Darstellung der Aussagen- und Prädikatenlogik, bei der die benötigten Begriffe präzise eingeführt und durch Beispiele veranschaulicht werden. Darauf beruhend werden Anwendungen der Logik in der Informatik, wie z. B. Resolution, Automatisches Beweisen und Logik-Programmierung behandelt. Zahlreiche Übungsaufgaben mit ausführlichen Lösungshinweisen erleichtern die Vertiefung des Lernstoffes.

CONCUR '94, Concurrency Theory

5th International Conference, Uppsala, Sweden, August 22-25, 1994 : Proceedings

Author: Bengt Jonsson,Joachim Parrow

Publisher: Springer


Category: Computer programs

Page: 528

View: 7583

"This volume constitutes the proceedings of the Fifth International Conference on Concurrency Theory, CONCUR '94, held at Uppsala, Sweden in August 1994. In total, 29 refereed research papers selected from 108 submissions for the conference are presented together with full papers or abstracts of the 5 invited talks by prominent speakers. The book contains recent results on all relevant aspects of concurrency research and thus competently documents the progress of the field since the predecessor conference CONCUR '93, the proceedings of which are published as LNCS 715"--PUBLISHER'S WEBSITE.

Scientific Applications of Language Methods

Author: Carlos Mart¡n Vide

Publisher: World Scientific

ISBN: 1848165447

Category: Mathematics

Page: 739

View: 8067

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.

Fuzzy Automata and Languages

Theory and Applications

Author: John N. Mordeson,Davender S. Malik

Publisher: CRC Press

ISBN: 9781420035643

Category: Computers

Page: 576

View: 7254

The huge number and broad range of the existing and potential applications of fuzzy logic have precipitated a veritable avalanche of books published on the subject. Most, however, focus on particular areas of application. Many do no more than scratch the surface of the theory that holds the power and promise of fuzzy logic. Fuzzy Automata and Languages: Theory and Applications offers the first in-depth treatment of the theory and mathematics of fuzzy automata and fuzzy languages. After introducing background material, the authors study max-min machines and max-product machines, developing their respective algebras and exploring properties such as equivalences, homomorphisms, irreducibility, and minimality. The focus then turns to fuzzy context-free grammars and languages, with special attention to trees, fuzzy dendrolanguage generating systems, and normal forms. A treatment of algebraic fuzzy automata theory follows, along with additional results on fuzzy languages, minimization of fuzzy automata, and recognition of fuzzy languages. Although the book is theoretical in nature, the authors also discuss applications in a variety of fields, including databases, medicine, learning systems, and pattern recognition. Much of the information on fuzzy languages is new and never before presented in book form. Fuzzy Automata and Languages incorporates virtually all of the important material published thus far. It stands alone as a complete reference on the subject and belongs on the shelves of anyone interested in fuzzy mathematics or its applications.