In the past twenty years state complexity has attracted much attention. This research had the following form: pick a class of regular languages or one of its subclasses, select a few operations, find an upper bound on the complexity of each operation, search for witnesses and prove they meet the upper bound. The outcome was a collection of largely disconnected results. But the field is changing: (a) It pays to study related classes and similar operations together; (b) other measures of complexity, such as the size of the syntactic semigroup or the number and complexity of atoms, should be considered; and (c) several of the measures are related. These developments will be discussed.
According to standard interpretations of quantum physics, quantum randomness is unique, true and perfect.
However, Ramsey theory shows that every sequence has infinitely many incomputable correlations, therefore, the concept of true or perfect randomness is mathematically vacuous. There are many degrees of randomness as there exist infinities of various sizes.
Challenging the quantum physics position with examples of incomputable correlations has almost no success with the physicist as incomputable quantities are not physically measurable.
First we will present an infinite computable set of correlations appearing in every Martin-Löf random sequence. We will continue with a brief review of results obtained from the recent interaction between algorithmic information theory and quantum physics.
This talk is warmly dedicated to Arto's 80th birthday. Arto has stimulated and encouraged me more than anybody else to study algorithmic randomness in a non-binary framework which paved the way to applications to quantum physics.
Watson-Crick D0L systems (WD0L systems) are variants of D0L systems with controlled derivations, where the control is inspired by the well-known phenomenon of Watson-Crick complementarity of the double helix of DNA. These systems are defined over a DNA-like alphabet, i.e., each letter has a complementary letter and this relation is symmetric. Depending on a trigger, a parallel rewriting step is applied either to the string or to its complementary string. In its generic form, a network of Watson-Crick D0L systems (an NWD0L system) is a finite set of WD0L systems over a common DNA-like alphabet which act on their own strings in parallel and after each derivation step send copies some of the generated words to the other nodes. During the years, NWD0L systems were studied from several aspects: for example, networks using different protocols for communication were compared, the growth of the number of strings under functioning was described. It was also shown that the so-called standard NWD0L systems form a class of computationally complete devices and are suitable tools for solving problems. Continuing these lines of investigations, we extend NWDOL systems with new features, describe their power, and demonstrate how some characteristics and phenomena typical for networks can be described and modeled using these constructs.
A finite coloring of an infinite word w over a finite alphabet A is any map c from the set of its non-empty factors into a finite set C (set of colors). This talk is an overview of recent results on the coloring of infinite words which have been obtained in collaboration with Elena Pribavkina and Luca Zamboni. The main problem which is considered is the following. Given a left-to-right infinite word w does there exist a finite coloring c of w with the property that each factorization w=U1U2U3 …, is not monochromatic, i.e., there exist positive integers i,j for which c(Ui)≠ c(Uj)? It has been proved that this problem has a positive answer for all non-uniformly recurrent words and then for almost all non-periodic words. Moreover, there is a positive answer also for various classes of uniformly recurrent words including all aperiodic balanced words (in particular Sturmian words). It is conjectured that the problem has a positive answer for all infinite non-periodic words.
Regular languages have many different characterizations in terms of automata, congruences, semigroups etc. We have a look at some results obtained mostly during the last three decades, namely characterizations using morphic compositions, equality sets and well orderings.
We will study connections between products of matrices and recursively enumerable sets. We will use the universal Diophantine representation of recursively enumerable sets of nonnegative integers due to Y. Matiyasevich combined with a method to use matrices to obtain the values taken by polynomials which has been widely used by A. Salomaa.
Great scientists do not only do great discoveries, they also try to pass their deep contextual knowledge to their students. Arto did it and still does it. He provides his views and knowledge to everybody interested though his fascinating textbooks. For several areas of computer science he was a pioneer in teaching them to us.
A one-dimensional cellular automaton is a discrete dynamical system where a sequence of symbols evolves synchronously according to a local update rule. We discuss simple update rules that make the automaton perform multiplications of numbers by a constant. If the constant and the number base are selected suitably the automaton becomes a universal pattern generator: all finite strings over its state alphabet appear from a finite seed. In particular we consider the automata that multiply by constants 3 and 3/2 in base 6. We discuss the connections of these automata to some difficult open questions in number theory, and we pose several further questions concerning pattern generation in cellular automata.
We introduce a novel method to computationally measure the distance between any two species based on unrelated short fragments of their genomic DNA. These pairwise species' distances are used to compute and output a two-dimensional "Map of Life", wherein each species is a point and the geometric distance between any two points reflects the degree of relatedness between the corresponding species. Such maps present compelling visual representations of relationships between species and could be used for species' classifications, new species identification, as well as for studies of evolutionary history.
Inspired by the acceptance modus for the weighted finite automata for quantitative languages (Chatterjee, Doyen, Henzinger: Quantitative languages.- LNCS 5213, 385 - 400, 2008) we let the weight of a path in the graph of such an automaton be dependent on the length of the path. (E. g., the weight of a path may be the average of the weight of its edges.) Summing up the weights of all paths from an initial to a final state gives then the behavior of such an automaton. For this acceptance modus, the theory of semiring - weighted finite automata is not applicable. But the algebraic theory of these weighted finite automata leads to weighted finite automata over hemirings (i. e., semirings without 1).
We develop a theory of Conway hemirings and show for weighted finite automata over Conway hemirings a Kleene Theorem that is applicable to the weighted finite automata with the new acceptance modus.
Formal languages have a prehistory, going back to Gauss, but brought in explicit form only in the nineties of the past century; a history beginning with Chomsky in 1956 and dominated by confusion and a new life, its Bourbaki correspondent, initiated in 1973, by Arto's monograph "Formal Languages' (Academic Press New York), dominated by clarity and rigor. Some significant steps of this itinerary are pointed out.
In 1914 Axel Thue posed a word problem for finitely presented semigroups named nowadays Thue systems. This decision problem was proved to be undecidable in 1947 by Andrey Markov and by Emil Post, independently. It was the very first case when a problem stated in ``pure'' mathematics was shown undecidable by just born computer science.
It turned out that computer science is more interested in so called semi-Thue systems. Techniques originally developed for constructing examples of undecidable Thue systems with a few defining relations lead to examples of undecidable semi-Thue systems defined by just 3 rules and for the undecidability of Post Correspondence Problem for 7 pairs of words.
Internet and other information and communication technologies (ICTs) are providing unprecedented easy access to information and collaboration, ushering in a revolution comparable to the invention of the printing press. Yet ICTs also have a dark side, like loss of privacy (consider NSA!). Still worse, it is becoming clear that heavy use of ICTs influences how we think. It is thus imperative to find out how to avoid that the spread of ICTs is turning us into dummies.
This is a quick story of my collaboration with Arto, starting with the total falling in love with formal languages theory through reading a typewritten manuscript of Arto's 1973 "Formal Languages" book, which I got already in 1973 from professor Solomon Marcus - I was his student then (and remain his student until now). We were in contact through ``classic" letters until April 1991 when I have visited Turku for the first time and met Arto. Soon after that the PRS (the acronym resulting from the first letters of Paun, Rozenberg, Salomaa but sematically translating into Pure Research Society) started to work and it is still active. In the second half of the nineteen-nineties, Turku experienced a real invasion of Romanian researchers. These were great scientific years for me - in particular, in the fall of 1998 the idea of membrane computing emerged (first presented in a TUCS report, in November 1998). After 2000, I moved to the South of Europe, but the contacts with Artolandia remained (with important consequences, such as having a Finish sauna in my house in Curtea de Arges, Romania).
We present a survey on results concerning the notion of first return words and of the operation of derivation in sets of words obtained by coding a geometric transformation.
The class of languages recognized by input-driven pushdown automata (IDPDA) retains many desirable closure and decision properties of the regular languages. A deterministic IDPDA equivalent to a nondeterministic IDPDA of size n may need 2Ω(n2) states (Alur, Madhusudan, J.ACM 2009). The IDPDA model is known in the literature also as a visibly pushdown automaton or a nested word automaton.
In the talk I survey joint work with Alexander Okhotin on the descriptional complexity of converting between nondeterministic, deterministic and unambiguous IDPDAs, as well as, IDPDAs employing limited nondeterminism.
For the first time in the history of Western University, on July 13, 2013, at its annual Spring convocation, the Chancellor of the University conferred the degree of Doctor of Science, honoris causa, to a computer scientist. The recipient was Prof. Arto Salomaa, for his outstanding contributions to Western; he was cited as a giant of theoretical computer science.
With the aid of historical pictures, details will be given for some of the reasons that this honor was bestowed on Prof. Salomaa, who is regarded now as one of the fathers of Canadian Theoretical Computer Science.
In particular, mentioned will be Prof. Salomaa's enormous contribution to teaching, supervising PhD students, bringing capable researchers and faculty to the fledgling Department of Computer Science, organizing international conferences at Western, inviting colloquium speakers, co-authoring with researchers at Western, and for nearly five decades becoming a frequent visitor and a valuable friend of all those who had the fortune to get to know him and his exceptionally talented family.