Model Theory, Computer Science, and Graph Polynomials: Festschrift in Honor of Johann A. Makowsky

by Klaus Meer (Editor), Alexander Rabinovich (Editor), Elena Ravve (Editor), Andrés Villaveces (Editor)

Overview

This festschrift honors Johann A. Makowsky on the occasion of his 75^th birthday. Gathering 24 research articles authored by scientific companions, friends, and colleagues, it covers a broad variety of areas to which Johann A. Makowsky made significant contributions himself. These include several areas of mathematical logic and its relevance for Computer Science including Graph polynomials, Algorithms for graph invariants, Algorithms and descriptive complexity theory, complexity of real and algebraic computations, Mathematical logic, Model theory, Design and theory of databases, Logic in computer science and AI and Logic programming. The volume is enriched with 4 biographical essays, and two contributions by the celebrant himself.

Product Details

ISBN-13:	9783031863189
Publisher:	Springer Nature Switzerland
Publication date:	08/06/2025
Series:	Trends in Mathematics
Pages:	577
Product dimensions:	6.10(w) x 9.25(h) x 0.00(d)

About the Author

Klaus Meer studied mathematics and received a Diploma, a Dr.rer.nat. and the Habilitation Degree from RWTH Aachen. After various research and temporary positions, including longer stays at CRM Barcelona, Université de Mons-Hainaut, MSRI Berkeley, Universidad de Chile in Santiago, and TU Chemnitz, in year 2000 he joined the IMADA Department at the University of Southern Denmark in Odense as Associate Professor. Further longer research stays led him to the University of Bonn and the ENS Lyon. In 2007 he was appointed full professor of Theoretical Computer Science at the TU Cottbus, now BTU Cottbus-Senftenberg. His main research interest is complexity theory with a focus on real number complexity. Since 2025 Meer is one of the Managing Editors of the journal ZML: Zeitschrift für Mathematische Logik und Grundlagen der Mathematik and since 2005 editor of the Journal of Complexity. Earlier, from 2011 until 2025 he was one of the Managing Editors of the journal Mathematical Logic Quarterly.

Professor Alexander Rabinovich is a full professor at the School of Computer Science and AI at Tel-Aviv University, specializing in logic in computer science. He earned his BSc from the Technion, followed by an MSc and PhD in Computer Science from Tel Aviv University. His research focuses on the applications of logical methods in computer science, particularly in areas such as formal verification, automata, monadic second-order logic and temporal logics. He has more than 140 publications in renowned journals and conferences, and serves as an editor of Fundamenta Informaticae.

Dr. Elena Ravve received her Bachelor degree in Russia in Applied Mathematics and Master and Doctor degrees from the Technion – Israel Institute of Technology, Computer Science department. Elena’s industrial experience includes different positions in the leading Hi-Tech companies in Israel: Freescale (Motorola Semiconductor), Intel, Tower-Jazz foundry. Elena has wide academic experience in Israel and abroad. Her research topics include but not limited to incremental, parallel and distributed computation and reasoning, graph polynomials, database theory, automated software and hardware design and verification. Today, Elena is working in Software Engineering department in one of the leading colleges in the North of Israel.

Andre's Villaveces is a professor of mathematics at Universidad Nacional de Colombia in Bogotá. He has held visiting positions at Carnegie Mellon University (2002-2003), the University of Helsinki (2007) and the University of Turin (2021), in addition to a post-doctoral position at the Hebrew University of Jerusalem (1996-1997). He has a Ph.D. in Mathematics of the University of Wisconsin (Madison), and a Master’s Degree in Mathematics of Universidad de los Andes (Bogotá). He works at the confluence of Model Theory and other areas of mathematics (Set Theory, and more recently, Learning Theory, Arithmetic Geometry and Mathematical Physics). He has had research funding from MinCiencias (Colombia). He was the recipient of the Best Young Scientist Award, Academia Colombiana de Ciencias Exactas, Físicas y Naturales (ACCEFYN) and Third World Academy of Sciences (TWAS) in August 2000. His editorial work includes three invited volumes (one for the Swedish philosophy journal Theoria, the current volume and another volume for Revista Colombiana de Matemáticas and the volume Logic Without Borders (Ontos Verlag, 2015. ISBN 978-1614517726). He has supervised two completed doctoral theses, three in progress. Also, about 35 undergraduate and masters’ thesis, most of them in Mathematics, one in Philosophy. He is the author of two academic books (one with Jouko Väänänen) and 23 research papers.

Table of Contents

- Part I: Personal Notes.- My writing.- Some personal remarks about Johann A. Makowsky.- The Swiss Connection.- From a Friend and Publisher.- From graph polynomials to the software industry Lessons from Janos.- Emancipatory Aspects of Learning and Teaching Mathematics.- Part II: Scientific Contributions.- Epsilon Calculus Provides Shorter Cut-Free Proofs.- Variations on a Theme of Makowsky.- Automatic structures and the problem of natural well-orderings.- On the Counting Complexity of the Cover Polynomial for Simple Graphs.- Polynomial Threshold Functions of Bounded Tree-Width: Some Explainability and Complexity Aspects.- Some Equalities are More Equal than Others.- On the bipartition polynomials for rooted caterpillars.- NP-completeness by first-order and quantifier-free interpretations and related topics.- Bounded languages over infinite alphabets.- Linear Algebraic Quantifiers.- A coarse Tutte polynomial for hypermaps.- Graph polynomials: some questions on the edge.- Pixelating relations and functions without adding substructures.- Reflection and Recurrence.- Provenance Analysis and Semiring Semantics for First-Order Logic.- Reversify any sequential algorithm.- Gentzen in the 3- and 4-valued jungle.- Characterizing Data Dependencies Then and Now.- On Consistency of Graphically Defined Specifications.- The path-bifurcation hierarchy does not collapse to 𝚺1 in infinite abelian groups.- Data with Logical and Statistical constraints.- Relating Information and Knowledge.- Science and Practice of Modelling.- Graph Polynomials and Local Graph Operations.