Pillars Of Computer Science: Essays Dedicated To Boris (boaz) Trakhtenbrot On The Occasion Of His 85th Birthday Essays Dedicated To Boris (boaz) Trakhtenbrot On The Occasion Of His 85th Birthday

From the reviews: "This festschrift is dedicated to Boris Trakhtenbrot on the occasion of his 85 th birthday. ... The volume covers a wide variety of papers on logic and the foundations of theoretical computer science, written by top people in the field. It is certainly worth acquiring for a library." (K. Lodaya, ACM Computing Reviews, January, 2009) Front Matter....Pages - From Logic to Theoretical Computer Science – An Update....Pages 1-38 Reminiscences....Pages 39-45 Boris A. Trakhtenbrot: Academic Genealogy and Publications....Pages 46-57 Symmetric Logic of Proofs....Pages 58-71 Synthesis of Monitors for Real-Time Analysis of Reactive Systems....Pages 72-86 A Framework for Formalizing Set Theories Based on the Use of Static Set Terms....Pages 87-106 Effective Finite-Valued Approximations of General Propositional Logics....Pages 107-129 Model Transformation Languages and Their Implementation by Bootstrapping Method....Pages 130-145 Modal Fixed-Point Logic and Changing Models....Pages 146-165 Fields, Meadows and Abstract Data Types....Pages 166-178 Why Sets?....Pages 179-198 The Church-Turing Thesis over Arbitrary Domains....Pages 199-229 Generalized Categorial Dependency Grammars....Pages 230-255 Temporal Verification of Probabilistic Multi-Agent Systems....Pages 256-265 Linear Recurrence Relations for Graph Polynomials....Pages 266-279 Artin’s Conjecture and Size of Finite Probabilistic Automata....Pages 280-291 Introducing Reactive Kripke Semantics and Arc Accessibility....Pages 292-341 On Partially Wellfounded Generic Ultrapowers....Pages 342-350 Some Results on the Expressive Power and Complexity of LSCs....Pages 351-366 Finite Dimensional Vector Spaces Are Complete for Traced Symmetric Monoidal Categories....Pages 367-385 Tree Automata over Infinite Alphabets....Pages 386-423 Connectives in Cumulative Logics....Pages 424-440 Reasoning in Dynamic Logic about Program Termination....Pages 441-456 The Grace of Quadratic Norms: Some Examples....Pages 457-459 Nested Petri Nets for Adaptive Process Modeling....Pages 460-474 Checking Temporal Properties of Discrete, Timed and Continuous Behaviors....Pages 475-505 Token-Free Petri Nets....Pages 506-520 Proof Search Tree and Cut Elimination....Pages 521-536 Symbolic Verification Method for Definite Iterations over Tuples of Altered Data Structures and Its Application to Pointer Programs....Pages 537-554 Categories of Elementary Sets over Algebras and Categories of Elementary Algebraic Knowledge....Pages 555-570 Selection and Uniformization Problems in the Monadic Theory of Ordinals: A Survey....Pages 571-588 The Scholten/Dijkstra Pebble Game Played Straightly, Distributedly, Online and Reversed....Pages 589-595 The Reaction Algebra: A Formal Language for Event Correlation....Pages 596-619 On Natural Non-dcpo Domains....Pages 620-634 Church’s Problem and a Tour through Automata Theory....Pages 635-655 From Monadic Logic to PSL....Pages 656-681 Back Matter....Pages - From Logic To Theorectical Computer Science, An Update -- Reminiscences -- Boris A. Trakhtenbrot: Academic Genealogy And Publications -- Symmetric Logic Of Proofs -- Synthesis Of Monitors For Real-time Analysis Of Reactive Systems -- Framework For Formalizing Set Theories Based On The Use Of Static Set Terms -- Effective Finite-valued Approximations Of General Propositional Logics -- Model Transformation Languages And Their Implementation By Bootstrapping Method -- Modal Fixed-point Logic And Changing Models -- Fields, Meadows, And Abstract Data Types -- Why Sets? -- Church-turing Thesis Over Arbitrary Domains -- Generalized Categorical Dependency Grammars -- Temporal Verification Of Probabilistic Multi-agent Systems -- Linear Recurrence Relations For Graph Polynomials -- Artin's Conjecture And Size Of Finite Probabilistic Automata -- Introducing Reactive Kripke Semantics And Arc Assembly -- On Partially Wellfounded Generic Ultrapowers --^ Some Results On The Expressive Power And Complexity Of Lscs -- Finite Dimensional Vector Spaces Are Complete For Traced Symmetric Monoidal Categories -- Tree Automata Over Infinite Alphabets -- Connectives In Cumulative Logics -- Reasoning In Dynamic Logic About Program Termination -- Grace Of Quadratic Norms: Some Examples -- Nested Petri Nets For Adaptive Process Modeling -- Checking Temporal Properties Of Discrete, Timed And Continuous Behaviors -- Token-free Petri Nets -- Proof Search Tree And Cut Elimination -- Symbolic Verification Method For Definite Iterations Over Tuples Of Altered Data Structures And Its Application To Pointer Programs -- Categories Of Elementary Sets Over Algebras And Categories Of Elementary Algebraic Knowledge -- Selection And Uniformization Problems In The Monadic Theory Of Ordinals: A Survey -- Scholten/dijkstra Pebble Game Played Straightly, Distributedly, Online, And Reversed -- Reaction Algebra: A Formal Language For Event Correlation --^ On Natural Non-depo Domains -- Church's Problem And A Tour Through Automata Theory -- From Monadic Logic To Psl. Arnon Avron, Nachum Dershowitz, Alexander Rabinovich (eds.). Includes Bibliographical References And Index. This festschrift volume is dedicated to Boris (Boaz) Trakhtenbrot on the occasion of his 85th birthday. For over half a century, Trakhtenbrot has been making seminal contributions to virtually all of the central areas of theoretical computer science. He is universally admired as a founding father and long-standing pillar of the discipline of computer science. On Friday, 28 April 2006, the School of Computer Science at Tel Aviv University held a "Computation Day Celebrating Boaz (Boris) Trakhtenbrot's Eighty-Fifth Birthday". As a follow-up to that event, his students and colleagues were asked to contribute to a volume in his honor and in recognition of his grand contributions to the field. The book opens with two historical overviews and a bibliography. These are followed by 33 thoroughly reviewed technical contributions. The broad range of topics covered include mathematical logic, logics for computer science, mathematics for computer science, automata and formal languages, asynchronous computation, semantics of programming languages, verification, and software engineering. This tapestry of subjects stands as testimony to the vast scope of Trakhtenbrot's achievements and the profound influence he has had on the field For Over Half A Century, Boris (boaz) Trakhtenbrot Has Made Seminal Contributions To Virtually All Of The Central Areas Of Theoretical Computer Science. This Festschrift Volume Readily Illustrates The Profound Influence He Has Had On The Field.