Johann A. Makowsky

Proceedings of the 32nd EACSL Annual Conference on Computer Science Logic, 2024

2023

Almost unimodal and real-rooted graph polynomials.

[BibT_eX]

[DOI]

Vsevolod Rakita

Eur. J. Comb., 2023

2022

On the Tutte and Matching Polynomials for Complete Graphs.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2022

2021

Some Thoughts on Computational Models: From Massive Human Computing to Abstract State Machines, and Beyond.

[BibT_eX]

[DOI]

Proceedings of the Logic, Computation and Rigorous Methods, 2021

2020

Harary polynomials.

[BibT_eX]

[DOI]

Orli Herscovici

Vsevolod Rakita

CoRR, 2020

To Yuri at 80 and More than 40 Years of Friendship.

[BibT_eX]

[DOI]

Proceedings of the Fields of Logic and Computation III, 2020

2019

On Weakly Distinguishing Graph Polynomials.

[BibT_eX]

[DOI]

Vsevolod Rakita

Discret. Math. Theor. Comput. Sci., 2019

The exact complexity of the Tutte polynomial.

[BibT_eX]

[DOI]

CoRR, 2019

A logician's view of graph polynomials.

[BibT_eX]

[DOI]

Ann. Pure Appl. Log., 2019

Can one design a geometry engine? - On the (un)decidability of certain affine Euclidean geometries.

[BibT_eX]

[DOI]

Ann. Math. Artif. Intell., 2019

On P-unique hypergraphs.

[BibT_eX]

[DOI]

R. X. Zhang

Australas. J Comb., 2019

2018

On sequences of polynomials arising from graph invariants.

[BibT_eX]

[DOI]

Eur. J. Comb., 2018

On the complexity of generalized chromatic polynomials.

[BibT_eX]

[DOI]

Adv. Appl. Math., 2018

The Undecidability of Orthogonal and Origami Geometries.

[BibT_eX]

[DOI]

Proceedings of the Logic, Language, Information, and Computation, 2018

2017

Keeping logic in the trivium of computer science: a teaching perspective.

[BibT_eX]

[DOI]

Anna Zamansky

Formal Methods Syst. Des., 2017

Can one design a geometry engine? On the (un)decidability of affine Euclidean geometries.

[BibT_eX]

[DOI]

CoRR, 2017

2016

Graph Polynomials: Towards a Comparative Theory (Dagstuhl Seminar 16241).

[BibT_eX]

[DOI]

Joanna A. Ellis-Monaghan

Andrew J. Goodall

Iain Moffatt

Dagstuhl Reports, 2016

Semantic Equivalence of Graph Polynomials Definable in Second Order Logic.

[BibT_eX]

[DOI]

Proceedings of the Logic, Language, Information, and Computation, 2016

On the Exact Learnability of Graph Parameters: The Case of Partition Functions.

[BibT_eX]

[DOI]

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

Hankel Matrices for Weighted Visibly Pushdown Automata.

[BibT_eX]

[DOI]

Proceedings of the Language and Automata Theory and Applications, 2016

2015

Teaching Logic for Computer Science: Are We Teaching the Wrong Narrative?

[BibT_eX]

[DOI]

CoRR, 2015

Efficient Computation of Generalized Ising Polynomials on Graphs with Fixed Clique-Width.

[BibT_eX]

[DOI]

Proceedings of the Topics in Theoretical Computer Science, 2015

Hankel Matrices: From Words to Graphs (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Language and Automata Theory and Applications, 2015

Logics of Finite Hankel Rank.

[BibT_eX]

[DOI]

Proceedings of the Fields of Logic and Computation II, 2015

2014

A representation theorem for (q-)holonomic sequences.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2014

On the location of roots of graph polynomials.

[BibT_eX]

[DOI]

N. K. Blanchard

Eur. J. Comb., 2014

Recurrence relations for graph polynomials on bi-iterative families of graphs.

[BibT_eX]

[DOI]

Eur. J. Comb., 2014

Connection Matrices and the Definability of Graph Parameters.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2014

2013

On the Location of Roots of Graph Polynomials.

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2013

Weighted Automata and Monadic Second Order Logic.

[BibT_eX]

[DOI]

Proceedings of the Proceedings Fourth International Symposium on Games, 2013

2012

Graph Polynomials: From Recursive Definitions to Subset Expansion Formulas.

[BibT_eX]

[DOI]

Emilia Katz

J. Log. Comput., 2012

Foreword.

[BibT_eX]

[DOI]

Sri Gopal Mohanty

Simone Rinaldi

Fundam. Informaticae, 2012

A Representation Theorem for Holonomic Sequences Based on Counting Lattice Paths.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2012

Fifty years of the spectrum problem: survey and new results.

[BibT_eX]

[DOI]

Bull. Symb. Log., 2012

A Computational Framework for the Study of Partition Functions and Graph Polynomials.

[BibT_eX]

[DOI]

Proceedings of the 14th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, 2012

Definability and Complexity of Graph Parameters (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic (CSL'12), 2012

BCNF via Attribute Splitting.

[BibT_eX]

[DOI]

Proceedings of the Conceptual Modelling and Its Theoretical Foundations, 2012

2011

The Universal Edge Elimination Polynomial and the Dichromatic Polynomial.

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2011

The enumeration of vertex induced subgraphs with respect to the number of components.

[BibT_eX]

[DOI]

Peter Tittmann

Eur. J. Comb., 2011

Model Theory in Computer Science: My Own Recurrent Themes.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 2011

2010

Complexity of the Bollobás-Riordan Polynomial. Exceptional Points and Uniform Reductions.

[BibT_eX]

[DOI]

Markus Bläser

Holger Dell

Theory Comput. Syst., 2010

An extension of the bivariate chromatic polynomial.

[BibT_eX]

[DOI]

Eur. J. Comb., 2010

Application of Logic to Integer Sequences: A Survey.

[BibT_eX]

[DOI]

Proceedings of the Logic, 2010

The Ackermann Award 2010.

[BibT_eX]

[DOI]

Damian Niwinski

Proceedings of the Computer Science Logic, 24th International Workshop, 2010

Definability of Combinatorial Functions and Their Linear Recurrence Relations.

[BibT_eX]

[DOI]

Proceedings of the Fields of Logic and Computation, 2010

2009

A Graph Polynomial Arising from Community Structure (Extended Abstract).

[BibT_eX]

[DOI]

Peter Tittmann

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2009

Connection Matrices for MSOL-Definable Structural Invariants.

[BibT_eX]

[DOI]

Proceedings of the Logic and Its Applications, Third Indian Conference, 2009

The Ackermann Award 2009.

[BibT_eX]

[DOI]

Alexander A. Razborov

Proceedings of the Computer Science Logic, 23rd international Workshop, 2009

On Counting Generalized Colorings.

[BibT_eX]

Boris Zilber

Proceedings of the Model Theoretic Methods in Finite Combinatorics, 2009

Application of logic to combinatorial sequences and their recurrence relations.

[BibT_eX]

Proceedings of the Model Theoretic Methods in Finite Combinatorics, 2009

2008

From a Zoo to a Zoology: Towards a General Theory of Graph Polynomials.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2008

Notions of Sameness by Default and their Application to Anaphora, Vagueness, and Uncertain Reasoning.

[BibT_eX]

[DOI]

Ariel Cohen

Michael Kaminski

J. Log. Lang. Inf., 2008

Counting truth assignments of formulas of bounded tree-width or clique-width.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2008

From Hilbert's program to a logic tool box.

[BibT_eX]

[DOI]

Ann. Math. Artif. Intell., 2008

Evaluations of Graph Polynomials.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2008

A Most General Edge Elimination Polynomial.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2008

Complexity of the Bollobás-Riordan Polynomial.

[BibT_eX]

[DOI]

Markus Bläser

Holger Dell

Proceedings of the Computer Science, 2008

The Ackermann Award 2008.

[BibT_eX]

[DOI]

Damian Niwinski

Proceedings of the Computer Science Logic, 22nd International Workshop, 2008

Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants.

[BibT_eX]

[DOI]

Proceedings of the Logic and Theory of Algorithms, 2008

Linear Recurrence Relations for Graph Polynomials.

[BibT_eX]

[DOI]

Proceedings of the Pillars of Computer Science, 2008

2007

From Hilbert's Program to a Logic Toolbox.

[BibT_eX]

[DOI]

Proceedings of the Logic for Programming, 2007

The Ackermann Award 2007.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 21st International Workshop, 2007

2006

Computing Graph Polynomials on Graphs of Bounded Clique-Width.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2006

The Ackermann Award 2006.

[BibT_eX]

[DOI]

Samson Abramsky

Erich Grädel

Proceedings of the Computer Science Logic, 20th International Workshop, 2006

From a Zoo to a Zoology: Descriptive Complexity for Graph Polynomials.

[BibT_eX]

[DOI]

Proceedings of the Logical Approaches to Computational Barriers, 2006

2005

Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2005

Clemens Lautemann: 1951-2005 An Obituary.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 19th International Workshop, 2005

The Ackermann Award 2005.

[BibT_eX]

[DOI]

Erich Grädel

Janos Makowsky

Alexander A. Razborov

Proceedings of the Computer Science Logic, 19th International Workshop, 2005

Indistinguishability by Default.

[BibT_eX]

Ariel Cohen

Michael Kaminski

Proceedings of the We Will Show Them! Essays in Honour of Dov Gabbay, Volume One, 2005

2004

On spectra of sentences of monadic second order logic with counting.

[BibT_eX]

[DOI]

J. Symb. Log., 2004

Algorithmic uses of the Feferman-Vaught Theorem.

[BibT_eX]

[DOI]

Ann. Pure Appl. Log., 2004

On the algebraic complexity of some families of coloured Tutte polynomials.

[BibT_eX]

[DOI]

Martin Lotz

Adv. Appl. Math., 2004

2003

Tree-width and the monadic quantifier hierarchy.

[BibT_eX]

[DOI]

Julian Mariño

Theor. Comput. Sci., 2003

The parametrized complexity of knot polynomials.

[BibT_eX]

[DOI]

Julian Mariño

J. Comput. Syst. Sci., 2003

Farrell polynomials on graphs of bounded tree width.

[BibT_eX]

[DOI]

Julian Mariño

Adv. Appl. Math., 2003

NCE Graph Grammars and Clique-Width.

[BibT_eX]

[DOI]

Alexander Glikson

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2003

The Specker-Blatter Theorem Revisited.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 9th Annual International Conference, 2003

2002

Fusion in Relational Structures and the Verification of Monadic Second-Order Properties.

[BibT_eX]

[DOI]

Bruno Courcelle

Math. Struct. Comput. Sci., 2002

2001

On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic.

[BibT_eX]

[DOI]

Bruno Courcelle

Udi Rotics

Discret. Appl. Math., 2001

Colored Tutte polynomials and Kaufman brackets for graphs of bounded tree width.

[BibT_eX]

[DOI]

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

2000

Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width.

[BibT_eX]

[DOI]

Bruno Courcelle

Udi Rotics

Theory Comput. Syst., 2000

On the Complexity of Combinatorial and Metafinite Generating Functions of Graph Properties in the Computational Model of Blum, Shub and Smale.

[BibT_eX]

[DOI]

Klaus Meer

Proceedings of the Computer Science Logic, 2000

1999

On the Clique-Width of Graphs with Few P4's.

[BibT_eX]

[DOI]

Udi Rotics

Int. J. Found. Comput. Sci., 1999

1998

Extensions for Open Default Theories via the Domain Closure Assumption.

[BibT_eX]

[DOI]

Michael Kaminski

Michael L. Tiomkin

J. Log. Comput., 1998

Dependency Preserving Refinements and the Fundamental Problem of Database Design.

[BibT_eX]

[DOI]

Data Knowl. Eng., 1998

Erratum to "Arity and Alternation in Second-Order Logic".

[BibT_eX]

Ann. Pure Appl. Log., 1998

Invariant Definability and P/poly.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 12th International Workshop, 1998

1997

Finitary Sketches.

[BibT_eX]

[DOI]

J. Symb. Log., 1997

Restrictions of Minimum Spanner Problems.

[BibT_eX]

[DOI]

Inf. Comput., 1997

The Fundamental Problem of Database Design.

[BibT_eX]

[DOI]

Proceedings of the SOFSEM '97: Theory and Practice of Informatics, 1997

Invariant Definability (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Computational Logic and Proof Theory, 5th Kurt Gödel Colloquium, 1997

1996

Arity and Alternation in Second-Order Logic.

[BibT_eX]

[DOI]

Ann. Pure Appl. Log., 1996

Translation Schemes and the Fundamental Problem of Database Design.

[BibT_eX]

[DOI]

Proceedings of the Conceptual Modeling, 1996

1995

On Average Case Complexity of SAT for Symmetric Distribution.

[BibT_eX]

[DOI]

Abraham Sharell

J. Log. Comput., 1995

Incremental Model Checking for Decomposable Structures (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1995, 1995

1994

Capturing Complexity Classes with Lindström Quantifiers.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1994, 1994

Arity vs. Alternation in Second Order Logic.

[BibT_eX]

[DOI]

Proceedings of the Logical Foundations of Computer Science, Third International Symposium, 1994

Logics Capturing Relativized Complexity Classes Uniformly.

[BibT_eX]

[DOI]

Proceedings of the Logical and Computational Complexity. Selected Papers. Logic and Computational Complexity, 1994

1993

Book Review: Predicate Transformer Semantics. By Ernest G. Manes. (Cambridge University Press, 1992, 233pp. ISBN 0-521-42036-9. $39.95).

[BibT_eX]

[DOI]

SIGACT News, 1993

Oracles and Quantifiers.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 7th Workshop, 1993

1992

Query Languages for Hierarchic Databases

[BibT_eX]

[DOI]

Inf. Comput., November, 1992

The Expressive Power of Side Effects in Prolog.

[BibT_eX]

[DOI]

J.-C. Gregoire

Shmuel Sagiv

J. Log. Program., 1992

Formal Interactive Menu Design.

[BibT_eX]

[DOI]

Jacob P. Ukelson

Interact. Comput., 1992

The Ehrenfeucht-Fraisse Games for Transitive Closure.

[BibT_eX]

[DOI]

A. Calò

Proceedings of the Logical Foundations of Computer Science, 1992

1991

Decidability of Finite Probablistic Propositional Dynamic Logics

[BibT_eX]

[DOI]

Michael L. Tiomkin

Inf. Comput., October, 1991

The Expressive Power of Transitive Closue and 2-way Multihead Automata.

[BibT_eX]

[DOI]

Yaniv Bargury

Proceedings of the Computer Science Logic, 5th Workshop, 1991

1990

Identifying Extended Entity-Relationship Object Structures in Relational Schemas.

[BibT_eX]

[DOI]

IEEE Trans. Software Eng., 1990

1989

Weak Second Order Characterizations of Various Program Verification Systems.

[BibT_eX]

[DOI]

Ildikó Sain

Theor. Comput. Sci., 1989

1988

On the existence of polynomial time algorithms for interpolation problems in propositional logic.

[BibT_eX]

[DOI]

Amos Israeli

Notre Dame J. Formal Log., 1988

Incremental Restructuring of Relational Schemas.

[BibT_eX]

[DOI]

Proceedings of the Fourth International Conference on Data Engineering, 1988

1987

Unification as a Complexity Measure for Logic Programming.

[BibT_eX]

[DOI]

Alon Itai

J. Log. Program., 1987

Why Horn Formulas Matter in Computer Science: Initial Structures and Generic Examples.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1987

Incremental Reorganization of Relational Databases.

[BibT_eX]

[DOI]

Proceedings of the VLDB'87, 1987

1986

On the Expressive Power of Data Dependencies.

[BibT_eX]

[DOI]

Moshe Y. Vardi

Acta Informatica, 1986

On the Equivalence of Weak Second Order and Nonstandard Time Semantics For Various Program Verification Systems

[BibT_eX]

Ildikó Sain

Proceedings of the Symposium on Logic in Computer Science (LICS '86), 1986

Musician - A Music Processing and Synthesis System.

[BibT_eX]

[DOI]

A. Ban

Proceedings of the 1986 International Computer Music Conference, 1986

Entity-Relationship Consistency for Relational Schemas.

[BibT_eX]

[DOI]

Nimrod Rotics

Proceedings of the ICDT'86, 1986

The Choice of Programming Primitives for SETL-Like Programming Languages.

[BibT_eX]

[DOI]

Proceedings of the ESOP 86, 1986

Computable Directory Queries.

[BibT_eX]

[DOI]

Proceedings of the CAAP '86, 1986

1985

Propositional Dynamic Logic with Local Assignments.

[BibT_eX]

[DOI]

Michael L. Tiomkin

Theor. Comput. Sci., 1985

Vopenka's Principle and Compact Logics.

[BibT_eX]

[DOI]

J. Symb. Log., 1985

A Proof Rule for Fair Termination of Guarded Commands

[BibT_eX]

[DOI]

Inf. Control., 1985

Why Horn Formulas Matter in Computer Science: Initial Structures and Generic Examples (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Software Development, 1985

1984

Characterizing Specification Languages which Admit Initial Semantics.

[BibT_eX]

[DOI]

Bernd Mahr

Theor. Comput. Sci., 1984

1983

Positive results in abstract model theory: a theory of compact logics.

[BibT_eX]

[DOI]

Saharon Shelah

Ann. Pure Appl. Log., 1983

An axiomatic approach to semantics of specification languages.

[BibT_eX]

[DOI]

Bernd Mahr

Proceedings of the Theoretical Computer Science, 1983

1981

The theorems of beth and Craig in abstract model theory II. Compact logics.

[BibT_eX]

[DOI]

Johann Shelah

Arch. Math. Log., 1981

Topological model theory with an interior operator: Consistency properties and back - and forth arguments.

[BibT_eX]

[DOI]

Martin Ziegler

Arch. Math. Log., 1981

Errata: Measuring the Expressive Power of Dynamic Logics: An Application of Abstract Model Theory.

[BibT_eX]

[DOI]

Proceedings of the Automata, 1981

Characterizing Data Base Dependencies.

[BibT_eX]

[DOI]

Proceedings of the Automata, 1981

1980

Embedded Implicational Dependencies and their Inference Problem.

[BibT_eX]

Ashok K. Chandra

Harry R. Lewis

Proceedings of the XP1 Workshop on Relational Database Theory, 30 June, 1980

Measuring the Expressive Power of Dynamic Logics: An Application of Abstract Model Theory.

[BibT_eX]

[DOI]

Proceedings of the Automata, 1980

1977

Completeness Theorems For Modal Model Theory With the Montague-Chang Semantics I.

[BibT_eX]

[DOI]

Annalisa Marcja

Math. Log. Q., 1977

Some model theory for monotone quantifiers.

[BibT_eX]

[DOI]