Theory Is Forever Essays Dedicated to Arto Salomaa on the Occasion of His 70th Birthday

This Festschrift celebrates the 70th birthday of Arto Kustaa Salomaa (born in Turku, Finland on June 6, 1934), one of the most in'uential researchers in theoretical computer science. Most ofhis researchconcernstheory - he is one of the founding fathers of formal language and automata theory, but he has also made important contributions to cryptography and natural computing. His approach to research in theoretical computer science is exemplary and inspirational for his students, collaborators, andthereadersofhispapersandbooks. Forhim, theroleoftheory(incomputer science) is to discover general rules of information processing that hold within computer science and in the world around us. One should not waste time on research concerning passing artifacts (or fashionable topics of the moment) in computer science - theory should be permanently predictive, insightful, and inspiring. That's why we chose the title "Theory is Forever." The main source of his in'uence on theoretical computer science is his publi- tions. Arto is a born writer - his papers and books are always most elegant. He has a unique gift for identifying the real essence of a research problem, and then presenting it in an incisive and eloquent way. He can write about a very involved formal topic and yet avoid a (much too common) overformalization. Many of his writings are genuine jewels and belong to the classics of theoreticalcomputer science. Theyhaveinspiredgenerationsofstudentsandresearchers. Indeed, even computers as well as computer science have learned a lot from Arto's publi- tions - this is nicely illustrated by DADARA on the cover of this volume.