Results and Trends in Theoretical Computer Science: Colloquium in Honor of Arto Salomaa, Graz, Austria, June 10 - 11, 1994. Proceedings (Lecture Notes in Computer Science, 812)

This volume is dedicated to Professor Arto Salomaa on the occasion of his 60th birthday. The 32 invited papers contained in the volume were presented at the festive colloquium, organized by Hermann Maurer at Graz, Austria, in June 1994; the contributing authors are well-known scientists with special relations to Professor Salomaa as friends, Ph.D. students, or co-authors. The volume reflects the broad spectrum of Professor Salomaa's research interests in theoretical computer science and mathematics with contributions particularly to automata theory, formal language theory, mathematical logic, computability, and cryptography. The appendix presents Professor Salomaa's curriculum vitae and lists the more than 300 papers and 9 books he published. Generalizing Cook's transformation to imperative stack programs....Pages 1-18 A rewriting of Fife's theorem about overlap-free words....Pages 19-29 Reconsidering the jeep problem or how to transport a birthday present to Salosauna....Pages 30-33 Learning picture sets from examples....Pages 34-43 Randomness as an invariant for number representations....Pages 44-66 Cooperating grammars' systems: Power and parameters....Pages 67-84 Parallel pattern generation with one-way communications....Pages 85-96 Dynamic labeled 2-structures with variable domains....Pages 97-123 Deciding the NTS property of context-free grammars....Pages 124-130 Homomorphic representations by products of tree automata....Pages 131-139 Identities and transductions....Pages 140-144 Decomposition of infinite labeled 2-structures....Pages 145-158 An iteration property of Lindenmayerian power series....Pages 159-168 Comparing descriptional and computational complexity of infinite words....Pages 169-182 On some open problems concerning the complexity of cellular arrays....Pages 183-196 Power of controlled insertion and deletion....Pages 197-212 From colonies to eco(grammar)systems....Pages 213-231 On the multiplicity equivalence problem for context-free grammars....Pages 232-250 On general solution of word equations....Pages 251-263 On (left) partial shuffle....Pages 264-278 Learning theoretical aspects is important but (Sometimes) dangerous....Pages 279-288 Bisimulation, games, and logic....Pages 289-306 Cryptographic protocols and voting....Pages 307-316 Cryptographic protocols for auctions and bargaining....Pages 317-324 On the size of components of cooperating grammar systems....Pages 325-343 An elementary algorithmic problem from an advanced standpoint....Pages 344-357 Event detection for ODES and nonrecursive hierarchies....Pages 358-371 Rediscovering pushdown machines....Pages 372-385 String matching algorithms and automata....Pages 386-395 Classifying regular languages by their syntactic algebras....Pages 396-409 On polynomial matrix equations X T =p(X) and X=p(X) Where all parameters are nonnegative....Pages 410-421 Gram's equation — A probabilistic proof....Pages 422-424 This volume is dedicated to Professor Arto Salomaa on the occasion of his 60th birthday. The 32 invited papers contained in the volume were presented at the festive colloquium, organized by Hermann Maurer at Graz, Austria, in June 1994; the contributing authors are well-known scientists with special relations to Professor Salomaa as friends, Ph. D. students, or co-authors. The volume reflects the broad spectrum of Professor Salomaa's research interests in theoretical computer science and mathematics with contributions particularly to automata theory, formal language theory, mathematical logic, computability, and cryptography. The appendix presents Professor Salomaa's curriculum vitae and lists the more than 300 papers and 9 books he published Stephen A. Cook described a transformation in 1971 that can, for instance, improve program running times from exponential to linear (as functions of their input size).