04929nam a22005295i 4500001001800000003000900018005001700027007001500044008004100059020001800100024002400118041000800142050001700150072001700167072002300184082001700207100003400224245020400258260006100462264006100523300003200584336002600616337002600642338003600668347002400704490005800728505136000786520166102146650002203807650001803829650003203847650003003879650002203909650003703931650003703968650004504005650004604050650002304096700003004119700003104149700003404180710003404214773002004248776003604268830005804304856003704362978-3-540-27812-2DE-He21320141014114344.0cr nn 008mamaa121227s2004 gw | s |||| 0|eng d a97835402781227 a10.1007/b987512doi aeng 4aQA75.5-76.95 7aUYZG2bicssc 7aCOM0370002bisacsh04a004.01512231 aKarhumäki, Juhani.eeditor.10aTheory Is Foreverh[electronic resource] :bEssays Dedicated to Arto Salomaa on the Occasion of His 70th Birthday /cedited by Juhani Karhumäki, Hermann Maurer, Gheorghe Păun, Grzegorz Rozenberg. 1aBerlin, Heidelberg :bSpringer Berlin Heidelberg,c2004. 1aBerlin, Heidelberg :bSpringer Berlin Heidelberg,c2004. aX, 286 p.bonline resource. atextbtxt2rdacontent acomputerbc2rdamedia aonline resourcebcr2rdacarrier atext filebPDF2rda1 aLecture Notes in Computer Science,x0302-9743 ;v31130 aDuality for Three: Ternary Symmetry in Process Spaces -- Mathematical Proofs at a Crossroad? -- Rational Relations as Rational Series -- Networks of Standard Watson-Crick D0L Systems with Incomplete Information Communication -- On the Size of Components of Probabilistic Cooperating Distributed Grammar Systems -- Remarks on Sublanguages Consisting of Primitive Words of Slender Regular and Context-Free Languages -- A Semiring-Semimodule Generalization of ?-Context-Free Languages -- Integer Weighted Finite Automata, Matrices, and Formal Power Series over Laurent Polynomials -- Two Models for Gene Assembly in Ciliates -- On Self-Dual Bases of the Extensions of the Binary Field -- On NFA Reductions -- Some Results on Directable Automata -- Rectangles and Squares Recognized by Two-Dimensional Automata -- Substitution on Trajectories -- Recombination Systems -- Algebraic Aspects of Parikh Matrices -- On Distributed Computing on Elliptic Curves -- On the Formal Modelling of Trust in Reputation-Based Systems -- Issues with Applying Cryptography in Wireless Systems -- On a Tomographic Equivalence Between (0,1)-Matrices -- P Systems with Tables of Rules -- Some Properties of Multistage Interconnection Networks -- Structural Equivalence of Regularly Extended E0L Grammars: An Automata Theoretic Proof -- Complexity of Evolving Interactive Systems. aThis 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. 0aComputer science. 0aLogic design. 0aElectronic data processing. 0aComputational complexity.14aComputer Science.24aComputation by Abstract Devices.24aLogics and Meanings of Programs.24aMathematical Logic and Formal Languages.24aDiscrete Mathematics in Computer Science.24aNumeric Computing.1 aMaurer, Hermann.eeditor.1 aPăun, Gheorghe.eeditor.1 aRozenberg, Grzegorz.eeditor.2 aSpringerLink (Online service)0 tSpringer eBooks08iPrinted edition:z9783540223931 0aLecture Notes in Computer Science,x0302-9743 ;v311340uhttp://dx.doi.org/10.1007/b98751