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.
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.
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.
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.
This book constitutes the proceedings of the 4th International Conference, LATA 2010, held in May 2010 in Trier, Germany. The 47 full papers presented were carefully selected from 115 submissions and focus on topics such as algebraic language theory , algorithmic learning, bioinformatics, computational biology, pattern recognition, program verification, term rewriting and tree machines.
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.
Like differentiability, convexity is a natural and powerful property of functions that plays a significant role in many areas of mathematics, both pure and applied. It ties together notions from topology, algebra, geometry and analysis, and is an important tool in optimization, mathematical programming and game theory. This book, which is the product of a collaboration of over 15 years, is unique in that it focuses on convex functions themselves, rather than on convex analysis. The authors explore the various classes and their characteristics and applications, treating convex functions in both Euclidean and Banach spaces. The book can either be read sequentially for a graduate course, or dipped into by researchers and practitioners. Each chapter contains a variety of specific examples, and over 600 exercises are included, ranging in difficulty from early graduate to research level.
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.
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.