Author: Jean Berstel,Dominique Perrin,Christophe Reutenauer
Publisher: Cambridge University Press
This major revision of Berstel and Perrin's classic Theory of Codes has been rewritten with a more modern focus and a much broader coverage of the subject. The concept of unambiguous automata, which is intimately linked with that of codes, now plays a significant role throughout the book, reflecting developments of the last 20 years. This is complemented by a discussion of the connection between codes and automata, and new material from the field of symbolic dynamics. The authors have also explored links with more practical applications, including data compression and cryptography. The treatment remains self-contained: there is background material on discrete mathematics, algebra and theoretical computer science. The wealth of exercises and examples make it ideal for self-study or courses. In summary, this is a comprehensive reference on the theory of variable-length codes and their relation to automata.
18th International Conference, CIAA 2013, Halifax, NS, Canada, July 16-19, 2013. Proceedings
Author: Stavros Konstantinidis
This book constitutes the thoroughly refereed papers of the 18th International Conference on Implementation and Application of Automata, CIAA 2013, held in Halifax, NS, Canada, in July 2013. The 25 revised full papers presented together with 3 invited papers and 7 short papers were carefully selected from 43 submissions. The papers cover various topics such as complexity of automata; compressed automata; counter automata; dictionary matching; edit distance; homing sequences; implementation; minimization of automata; model checking; parsing of regular expressions; partial word automata; picture languages; pushdown automata; queue automata; reachability analysis for software verification; restarting automata; transducers; tree automata; weighted automata; XML streams.
Computers by Adrian-Horia Dediu,Jan Janoušek,Carlos Martín-Vide,Bianca Truthe
This book constitutes the refereed proceedings of the 10th International Conference on Language and Automata Theory and Applications, LATA 2016, held in Prague, Czech Republic, in March 2016. The 42 revised full papers presented together with 5 invited talks were carefully reviewed and selected from 119 submissions. The papers cover the following topics: algebraic language theory; algorithms for semi-structured data mining, algorithms on automata and words; automata and logic; automata for system analysis and program verification; automata networks, concurrency and Petri nets; automatic structures; cellular automata, codes, combinatorics on words; computational complexity; data and image compression; descriptional complexity; digital libraries and document engineering; foundations of finite state technology; foundations of XML; fuzzy and rough languages; grammatical inference and algorithmic learning; graphs and graph transformation; language varieties and semigroups; parallel and regulated rewriting; parsing; patterns; string and combinatorial issues in computational biology and bioinformatics; string processing algorithms; symbolic dynamics; term rewriting; transducers; trees, tree languages and tree automata; weighted automata.
10th International Conference, FORMATS 2012, London, UK, September 18-20, 2012, Proceedings
Author: Marcin Jurdzinski,Dejan Nickovic
This book constitutes the refereed proceedings of the 10th International Conference on Formal Modeling and Analysis of Timed Systems, FORMATS 2012, held in London, UK in September 2012. The 16 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 34 submissions. The book covers topics of foundations and semantics, methods and tools, techniques, algorithms, hybrid automata, appilcations, real-time software and hardware circuits.
In this book, which was originally published in 1985, Arto Salomaa gives an introduction to certain mathematical topics central to theoretical computer science: computability and recursive functions, formal languages and automata, computational complexity and cryptography.
This series is devoted to significant topics or themes that have wide application in mathematics or mathematical science and for which a detailed development of the abstract theory is less important than a thorough and concrete exploration of the implications and applications. Books in the Encyclopedia of Mathematics and its Applications cover their subjects comprehensively. Less important results may be summarised as exercises at the ends of chapters, For technicalities, readers can be referred to the bibliography, which is expected to be comprehensive. As a result, volumes are encyclopedic references or manageable guides to major subjects.
Introduction to Convolutional Codes with Applications is an introduction to the basic concepts of convolutional codes, their structure and classification, various error correction and decoding techniques for convolutionally encoded data, and some of the most common applications. The definition and representations, distance properties, and important classes of convolutional codes are also discussed in detail. The book provides the first comprehensive description of table-driven correction and decoding of convolutionally encoded data. Complete examples of Viterbi, sequential, and majority-logic decoding technique are also included, allowing a quick comparison among the different decoding approaches. Introduction to Convolutional Codes with Applications summarizes the research of the last two decades on applications of convolutional codes in hybrid ARQ protocols. A new classification allows a natural way of studying the underlying concepts of hybrid schemes and accommodates all of the new research. A novel application of fast decodable invertible convolutional codes for lost packet recovery in high speed networks is described. This opens the door for using convolutional coding for error recovery in high speed networks. Practicing communications, electronics, and networking engineers who want to get a better grasp of the underlying concepts of convolutional coding and its applications will greatly benefit by the simple and concise style of explanation. An up-to-date bibliography of over 300 papers is included. Also suitable for use as a textbook or a reference text in an advanced course on coding theory with emphasis on convolutional codes.
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.
Research in computational group theory, an active subfield of computational algebra, has emphasised three areas: finite permutation groups, finite solvable groups, and finitely presented groups. This book deals with the third of these areas. The author emphasises the connections with fundamental algorithms from theoretical computer science, particularly the theory of automata and formal languages, computational number theory, and computational commutative algebra. The LLL lattice reduction algorithm and various algorithms for Hermite and Smith normal forms from computational number theory are used to study the abelian quotients of a finitely presented group. The work of Baumslag, Cannonito and Miller on computing nonabelian polycyclic quotients is described as a generalisation of Buchberger's Gröbner basis methods to right ideals in the integral group ring of a polycyclic group. Researchers in computational group theory, mathematicians interested in finitely presented groups and theoretical computer scientists will find this book useful.
8th International Conference, CIAA 2003, Santa Barbara, CA, USA, July 16-18, 2003. Proceedings
Author: Oscar H. Ibarra,Zhe Dang
Category: Machine theory
Automata theory is the foundation of computer science. Its applications have spread to almost all areas of computer science and many other disciplines. In addition, there is a growing number of software systems designed to manipulate automata, regular expressions, grammars, and related structures. This volume contains 24 regular papers from the 8th International Conference on Implementation and Application of Automata (CIAA 2003) held in Santa Barbara, CA, USA, in July 2003 covering various topics in the theory, implementation, and application of automata and related structures. It also includes the abstracts of two invited lectures as well as the abstracts of the poster papers displayed during the conference.
Computer science by Edwin D. Reilly,Anthony Ralston,David Hemmendinger
Author: Edwin D. Reilly,Anthony Ralston,David Hemmendinger
Category: Computer science
The Encyclopedia of Computer Science is the definitive reference for anyone who works with computers, computing, and computer science. This new edition has 2,000 pages containing over 623 fully updated articles by internationally known computing experts. Students, professionals, and lay readers quickly find all the information they need in one, easy-to-use volume for clear, concise explanations of the latest technology and its applications - including past, present, and predicted future trends in computer science. Arranged alphabetically, the 623 articles are classified into sections covering the main themes of computing: hardware, software, computer graphics, information and data, mathematics of computing, methodologies, applications and computing milieu. The encyclopedia also includes extensive appendices, and name and subject indexes.
Internationally recognised researchers look at developing trends in combinatorics with applications in the study of words and in symbolic dynamics. They explain the important concepts, providing a clear exposition of some recent results, and emphasise the emerging connections between these different fields. Topics include combinatorics on words, pattern avoidance, graph theory, tilings and theory of computation, multidimensional subshifts, discrete dynamical systems, ergodic theory, numeration systems, dynamical arithmetics, automata theory and synchronised words, analytic combinatorics, continued fractions and probabilistic models. Each topic is presented in a way that links it to the main themes, but then they are also extended to repetitions in words, similarity relations, cellular automata, friezes and Dynkin diagrams. The book will appeal to graduate students, research mathematicians and computer scientists working in combinatorics, theory of computation, number theory, symbolic dynamics, tilings and stringology. It will also interest biologists using text algorithms.
Computers by Javier Leach Albert,Burkhard Monien,Mario Rodriguez Artalejo
18th International Colloquium, Madrid, Spain, July 8-12, 1991. Proceedings
Author: Javier Leach Albert,Burkhard Monien,Mario Rodriguez Artalejo
This volume contains the proceedings of ICALP '91, the 18th annual summer conference sponsored by the European Association for Theoretical Computer Science (EATCS). ICALP stands for International Colloquium on Automata, Languages, and Programming, and this conference series covers all important areas of theoretical computer science, such as: computability, automata, formal languages, data types and structures, theory of databases and knowledge bases, semantics of programming languages, program specification, transformation and verification, foundations of logic and functional programming, theory of logical design and layout, parallel and distributed computation, theory of concurrency, symbolic and algebraic computation, term rewriting systems, computational geometry, cryptography, and theory of robotics.