Jewels are Forever Springer Berlin Heidelberg New York Barcelona Hong Kong London Milan Paris Singapore Tokyo Arto Salomaa Juhani Karhumaki • Hermann Maurer Gheorghe Paun· Grzegorz Rozenberg (Eds.) Jewels are Forever Contributions on Theoretical Computer Science in Honor of Arto Salomaa With 20 Figures " Springer Editors Professor Dr. Juhani Karhumaki Dr. Gheorghe Paun Department of Mathematics Institute of Mathematics and Turku Centre for Computer Science Romanian Academy of Sciences University of Turku PO Box 1-764 FIN-20014 Turku, Finland RO-70700 Bucharest, Romania [email protected] [email protected] Professor Dr. Hermann Maurer Professor Dr. Grzegorz Rozenberg Institutes for Information Processing Department of Computer Science and Computer Supported Media (IICM) Leiden University Technical University of Graz PO Box 9512 Schiessstattgasse 4a 2300 RA Leiden, The Netherlands A-SOlO Graz, Austria [email protected] [email protected] Frontispiece (p. 11): Digital photographic image by Henrik Duncker and Yrjo Tuunanen, 1994, ©Media Lab, University of Art and Design Helsinki Library of Congress Cataloging-in-Publication Data applied for Die Deutsche Bibliothek - CIP-Einheitsaufnahme Jewels are forever: contributions on theoretical computer science in honor of Arto Salomaa/Juhani Karhumaki ... (ed.). -Berlin; Heidelberg; New York; Barcelona; Hong Kong; London; Milan; Paris; Singapore; Tokyo: Springer, 1999 ISBN-13:978-3-642-64304-0 e-ISBN-13:978-3-642-60207-8 DOl: 10.1007/978-3-642-60207-8 ISBN-13:978-3-642-64304-0 Springer-Vedag Berlin Heidelberg New York This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are liable for prosecution under the German Copyright Law. © Springer-Verlag Berlin Heidelberg 1999 Softcover reprint of the hardcover 1st edition 1999 The use of general descriptive names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Cover Design: Klinkel + Lopka, Werbeagentur, Heidelberg Typesetting: Camera ready by the editors SPIN 10727442 45/3142 - 5 432 10-Printed on acid-free paper Preface This volume is dedicated to Professor Arto Salomaa, a towering figure of theoretical computer science, on the occasion of his 65th birthday. His sci entific contributions and influence are enormous - we refer the reader to the following Laudation for an account of his scientific achievements. The book is a tribute to Arto by the theoretical computer science com munity. It includes the contributions of many outstanding scientists, and it covers most of Arto's many research areas. Due to its representative selection of classic topics and cutting edge trends in theoretical computer science it constitutes a comprehensive state-of-the-art survey. We feel very honored that we have been given the opportunity to edit this book - we also feel privileged to be his friends. We are indebted to all contributors for paying tribute to Arto through this book. We thank Dr. H. Wossner and Mrs. 1. Mayer from Springer-Verlag for a perfect cooperation in producing this volume. Our special thanks go to Mr. M. Hirvensalo and Mr. A. Lepisto, the "2nd generation Ph.D. students" of Arto, for their work on this book. Turku, April 1999 Juhani Karhumiiki Hermann Maurer Gheorghe Paun Grzegorz Rozenberg Contents Laudation for Arto Salomaa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. XI Bibliography of Arto Salomaa ............................... XIII Part I. Automata I: Finite State Machines Semilattices of Fault Semiautomata. . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Janusz A. Brzozowski, Helmut Jurgensen Thompson Languages. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 16 Dora Giammarresi, Jean-Luc Ponty, Derick Wood On Some Special Classes of Regular Languages . . . . . . . . . . . . . .. 25 BalO.zs Imreh, Masami Ito Synchronized Shuffle and Regular Languages ................. 35 Michel Latteux, Yves Roos Synchronization Expressions: Characterization Results and Implementation ................ 45 Kai Salomaa, Sheng Yu Part II. Automata II: More General Devices Uniformization of Rational Relations. ..... . . .. . . .. . . ......... 59 Christian ChojJrut, Serge Grigorieff Tree-Walking Pebble Automata. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 72 Joost Engelfriet, Hendrik Jan Hoogeboom Counter Machines: Decision Problems and Applications ...... 84 Oscar H. Ibarra, Jianwen Su On the Equivalence of Finite Substitutions and Transducers .. 97 Juhani K arhumiiki, Leonid P. Lisovik VIII Contents Complementation of Biichl Automata Revisited .............. 109 Wolfgang Thomas Part III. Automata with Multiplicities Languages Accepted by Integer Weighted Finite Automata ... 123 Vesa Halava, Tero Harju A Power Series Approach to Bounded Languages ............. 135 Juha Honkala Full Abstract Families of Tree Series I ........................ 145 Werner Kuich Linear Automata, Rational Series and a Theorem of Fine and Wilf .............................. 157 Giovanna Melideo, Cesidia Pasquarelli, Stefano Varricchio Part IV. Formal Languages Numerical Parameters of Evolutionary Grammars . . . . . . . . . . .. 171 Jurgen Dassow Iterated GSM Mappings: A Collapsing Hierarchy ............. 182 Vincenzo Manca, Carlos Martin-Vide, Gheorghe Paun On the Length of Words ...................................... 194 Solomon Marcus An Insertion into the Chomsky Hierarchy? ................... 204 Robert McNaughton Word Length Controlled DTOL Systems and Slender Languages ........................... , ...... " ... 213 Taishin Yasunobu Nishida Part V. Algorithms and Complexity Program-Size Complexity of Initial Segments and Domination Reducibility ................................. 225 Cristian S. Calude, Richard J. Coles Stability of Approximation Algorithms and the Knapsack Problem ................................... 238 Juraj Hromkovic Contents IX Some Examples of Average-case Analysis by the Incompressibility Method ............................. 250 Tao Jiang, Ming Li, Paul Vittlnyi Complexity of Language Recognition Problems for Compressed Words ............................. 262 Wojciech Plandowski, Wojciech Rytter Algorithms on Continued Fractions .......................... 273 Octavian Soldea, Azaria Paz Part VI. Combinatorics of Words On the Index of Sturmian Words ............................. 287 Jean Berstel Repetitions and Boxes in Words and Pictures ................ 295 Arturo Carpi, Aldo de Luca Small Aperiodic Sets of Triangular and Hexagonal Tiles ...... 307 Karel CuZik II Quadratic Word Equations ................................... 314 Volker Diekert, John Michael Robson Fair and Associative Infinite Trajectories ..................... 327 Alexandru Mateescu, George Daniel Mateescu Forbidden Factors in Finite and Infinite Words . . . . . . . . . . . . . . . 339 Filippo Mignosi, Antonio Restivo, Marinella Sciortino Part VII. Novel Directions Reversible :tyIolecular Computation in Ciliates ................ 353 Lila Kari, Jarkko Kari, Laura F. Landweber Logic, Probability, and Rough Sets ........................... 364 Zdzislaw Pawlak List of Contributors .......................................... 375 Laudation for Arto Salomaa Arto Kustaa Salomaa was born in Turku, Finland, on June 6, 1934. He pub lished his first paper in 1959, and since then he has published about 300 papers and 11 books, and has edited 15 books - see the following Bibliogra phy. He has had enormous influence on theoretical computer science and is certainly one of the founding fathers of formal language and automata theory. His influence on theoretical computer science extends far beyond his writ ings. He has supervised 24 Ph.D. students in Finland, Denmark and Canada, and many of them have become top scientists in various areas of computer science. He is on the editorial board of some fifteen international journals and book series and has been a member of program committees for almost all important conferences in theoretical computer science in Europe. Arto is a very stimulating colleague, and he has cooperated with many scientists allover the world - his list of co-authors includes some 53 names. His contributions to theoretical computer science have been recognized in many ways. He must be one of the most decorated computer scientists - he has been awarded six Honorary Doctorates (in four countries) and has received many scientific awards. He is a member of Academia Europaea, the Academy of Sciences of Finland, and the Hungarian Academy of Sciences. He was the President of the European Association for Theoretical Computer Science (EATCS) from 1979 until 1986, and had an enormous influence on this organisation through many other functions. Some of the honors he has received are quite unusual. On one of his trips a Maori group north of Auck land put on a Powhiri, a ceremony usually conducted as a way of honoring persons of the importance of the Queen of England. Arto may well be the only computer scientist to whom such a tribute has ever been paid. From all the facts listed above it must be clear that in celebrating Arto's 65th birthday we pay tribute to a towering figure of theoretical computer science. There is no doubt that theoretical computer science owes a lot to Arto Salomaa. Throughout his scientific career Arto has had many offers from top uni versities allover the world. However, he has decided that Turku is his home town and that this is where he wants to have his base. He received his Master of Science from the University of Turku in 1956, and although he did his grad- XII Laudation for Arto Salomaa uate studies in Berkeley, he defended his Ph.D. at the University of Turku in 1960. He became a full professor at Turku University in 1966. Since then he has made Thrku a real place of excellence in theoretical computer science, and certainly the world capital in formal language and automata theory. Although Thrku was always his home base, he has traveled extensively. He spent long periods of time at the universities of Western Ontario and Waterloo in Canada and the University of Aarhus in Denmark. He has also had quite lengthy research stays, among others, at the universities of Auckland, Graz, Karlsruhe, Leiden, Szeged, and Vienna. He has lectured at more than 150 universities and research centers all over the world - he is a very inspiring lecturer. His lectures and his books demonstrate a unique ability: he is always able to pick out from the sea of results the real jewels, and then present them in the way that jewels deserve (quite often the jewels are also created by him). As a matter offact, one of his most frequently cited books is "Jewels of Formal Language Theory". That's why we thought that the title "Jewels are Forever" fits this book very well. Thrku, April 1999 Juhani Karhumiiki Hermann Maurer Gheorghe Piiun Grzegorz Rozenberg