Cristian Calude Bücher

The first edition of the monograph by Cristian Calude, published in 1994, marked a significant milestone in algorithmic information theory, which has seen vigorous growth in recent years. The book presents original research that enriches the field, making it suitable for both researchers and as a textbook. It is self-contained, with all proofs included, eliminating the need for additional sources in classroom settings. The second edition reflects continued advancements in the study, featuring numerous new results, examples, exercises, and open problems. Notably, it introduces two new chapters: “Computably Enumerable Random Reals” and “Randomness and Incompleteness.” A comprehensive new bibliography enhances its value for researchers. The new findings on computably enumerable random reals and Omega Numbers significantly contribute to its utility as a textbook. The author’s direct involvement in these results, published in prestigious journals like Nature and New Scientist, underscores the book's relevance and impact in the field.

This volume contains the papers presented at the Third Combinatorics, Computability and Logic (DMTCS'01) conference, These papers cover topics such as abstract data types and specifications algorithms and data structures automata and formal languages computability among others.

This book collects personal accounts and reflections of fourteen eminent scientists who have dedicated themselves to the craft of theoretical computer science. Contributions focus on the authors' specific interests, experiences, and reminiscences. The emerging picture, which is just one among many, should be a catalyst for further developments and continuations.

The finite - infinite interplay is central in human thinking, from ancient philosophers and mathematicians (Zeno, Pythagoras), to modern mathe­ matics (Cantor, Hilbert) and computer science (Turing, Godel). Recent developments in mathematics and computer science suggest a) radically new answers to classical questions (e. g. , does infinity exist?, where does infinity come from?, how to reconcile the finiteness of the human brain with the infinity of ideas it produces?), b) new questions of debate (e. g. , what is the role played by randomness?, are computers capable of handling the infinity through unconventional media of computation?, how can one approximate efficiently the finite by the infinite and, conversely, the infinite by finite?). Distinguished authors from around the world, many of them architects of the mathematics and computer science for the new century, contribute to the volume. Papers are as varied as Professor Marcus' activity, to whom this volume is dedicated. They range from real analysis to DNA com­ puting, from linguistics to logic, from combinatorics on words to symbolic dynamics, from automata theory to geography, and so on, plus an incursion into the old history of conceptions about infinity and a list of philosophical "open problems". They are mainly mathematical and theoretical computer science texts, but not all of them are purely mathematical.

This book is dedicated to Hermann Maurer on the occasion of his 70th birthday. The title word Rainbow reflects the beauty and variety of the achievements of this outstanding scientist, and also the diversity and depth of current research in computer science. The high admiration that Professor Maurer enjoys in the computer science community all over the world was witnessed by the enthusiastic response received to the request to contribute to this book. The contributors are leading researchers, also representing the diversity of computer science. The research areas included in the book range from Automata, Formal Languages and Computability to various aspects of the Practice of Computer Science, as well as from Algorithmics to Learning. The book consists of a brief Preface describing the achievements of Professor Maurer, followed by twenty articles roughly grouped together according to their topics. Most of the articles are written in a style understandable to a wider audience. The book is useful to anyone interested in recent developments in computer science.

This book constitutes the refereed proceedings of the 6th FIP WG 2.2 International Conference, TCS 2010, held as a part of the 21th World Computer Congress, WCC 2010, in Brisbane, Australia, in September 2010. The 23 revised full papers presented, together with 4 invited talks, were carefully reviewed and selected from 39 submissions. TCS 2010 deals with topics focused at but not limited to algorithms, complexity, models of computation, logic, semantics, specification and verification, power-awareness issues in wireless networks, data mining, knowledge discovery, multiprocessor issues as well as AI issues.

This book constitutes the refereed proceedings of the 4th International Conference on Unconventional Computation, UC 2005, held in Sevilla, Spain in September 2005. The conference formerly was named Unconventional Models of Computation (UMC). The 19 revised full papers presented together with 5 invited full papers were carefully reviewed and selected for inclusion in the book. All major areas of unconventional computing models are covered in theory as well as in experiments and applications. Topics addressed are: natural computing including quantum, cellular, molecular, neural and evolutionary computing; chaos and dynamical systems based computing; and various proposals for computations that go beyond the Turing model.

This collection features a range of invited and contributed papers that explore various topics in graph theory, automata, and computational models. It includes surveys on recognizable sets of graphs and hypergraphs, as well as discussions on parameterized complexity. Key concepts such as reaction systems and a Kleene theorem for communicating automata are addressed, alongside algebraic and topological models related to DNA recombinant processes. Contributions delve into regular expressions for two-dimensional languages, competence in CD grammar systems, and the correspondence between dot-depth and the polynomial hierarchy. New characterizations of languages through input reversals and iterated pushdown automata are presented, along with studies on maximum coefficients of rational formal series. The collection also examines codes defined by bio-operations, avoidable sets, and well quasi-orders, alongside a focus on ciliate bio-operations and language families. Additionally, topics such as semantic shuffles, Sturmian graphs, and firing squad synchronization problems are discussed. The power of maximal parallelism in P systems is highlighted, along with efficient algorithms for pattern matching in context-free grammars. The complexity of various automata, including left-monotone deterministic restarting automata and finite automata in two-dimensional environments, is analyzed. Other significant discussions include the role of

InhaltsverzeichnisInvited Papers.Two Philosophical Applications of Algorithmic Information Theory.Covering and Secret Sharing with Linear Codes.Combinatorial Problems Arising in SNP and Haplotype Analysis.Cellular Automata and Combinatoric Tilings in Hyperbolic Spaces. A Survey.Generating Gray Codes in O(1) Worst-Case Time per Word.Contributed Papers.Listing Vertices of Simple Polyhedra Associated with Dual LI(2) Systems.Automatic Forcing and Genericity: On the Diagonalization Strength of Finite Automata.On the Order Dual of a Riesz Space.A Finite Complete Set of Equations Generating Graphs.ECO Method and the Exhaustive Generation of Convex Polyominoes.Regular Expressions with Timed Dominoes.On Infinitary Rational Relations and Borel Sets.Efficient Algorithms for Disjoint Matchings among Intervals and Related Problems.On Functions and Relations.Paths Coloring Algorithms in Mesh Networks.Finite State Strategies in One Player McNaughton Games.On Algebraic Expressions of Series-Parallel and Fibonacci Graphs.Boolean NP-Partitions and Projective Closure.On Unimodality of Independence Polynomials of Some Well-Covered Trees.A Coloring Algorithm for Finding Connected Guards in Art Galleries.An Analysis of Quantified Linear Programs.An Efficient Branch-and-Bound Algorithm for Finding a Maximum Clique.On the Monotonic Computability of Semi-computable Real Numbers.

InhaltsverzeichnisStructures and Bio-language to Simulate Transition P Systems on Digital Computers.Gamma and the Chemical Reaction Model: Fifteen Years After.Visual Multiset Rewriting: Applications to Diagram Parsing and Reasoning.Multiset Automata.Parikh Mapping and Iteration.Multiset Constraints and P Systems.Toward a Formal Macroset Theory.Normal Forms of Grammars, Finite Automata, Abstract Families, and Closure Properties of Multiset Languages.On Multisets in Database Systems.Tolerance Multisets.Fuzzy Multisets and Their Generalizations.Universality Results for Some Variants of P Systems.Multiset and K-Subset Transforming Systems.On P Systems with Active Membranes Solving the Integer Factorization Problem in a Polynomial Time.The Linear Theory of Multiset Based Dynamic Systems.Artificial Life Applications of a Class of P Systems: Abstract Rewriting Systems on Multisets.Mathematics of Multisets.