Model Theory, Computer Science, and Graph Polynomials : Festschrift in Honor of Johann A. Makowsky / edited by Klaus Meer, Alexander Rabinovich, Elena Ravve, Andrés Villaveces.

Format:

Book

Author/Creator:

Meer, Klaus.

Contributor:

Rabinovich, Alexander.

Ravve, Elena.

Villaveces, Andrés.

Series:

Trends in Mathematics, 2297-024X

Language:

English

Subjects (All):

Logic, Symbolic and mathematical.

Mathematical Logic and Foundations.

Local Subjects:

Mathematical Logic and Foundations.

Physical Description:

1 online resource (944 pages)

Edition:

1st ed. 2025.

Place of Publication:

Cham : Springer Nature Switzerland : Imprint: Birkhäuser, 2025.

Summary:

This festschrift honors Johann A. Makowsky on the occasion of his 75th 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.

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.

Notes:

Description based on publisher supplied metadata and other sources.

ISBN:

3-031-86319-4

OCLC:

1534804126