Model Theory, Computer Science, and Graph Polynomials -

. .

Editeur : Springer International Publishing Ag

Langue : Anglais

Parution : 01/08/2025

Format : Moyen, de 350g à 1kg

Nombre de pages : 596.0

ISBN : 9783031863189

Résumé :
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....

Biographie:
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.

...

Sommaire:
- 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....