Johann A. Makowsky

According to our database1, Johann A. Makowsky
  • authored at least 126 papers between 1977 and 2018.
  • has a "Dijkstra number"2 of three.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2018
On sequences of polynomials arising from graph invariants.
Eur. J. Comb., 2018

2017
Keeping logic in the trivium of computer science: a teaching perspective.
Formal Methods in System Design, 2017

On the complexity of generalized chromatic polynomials.
CoRR, 2017

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

On the exact learnability of graph parameters: The case of partition functions.
CoRR, 2016

Semantic Equivalence of Graph Polynomials Definable in Second Order Logic.
Proceedings of the Logic, Language, Information, and Computation, 2016

On the Exact Learnability of Graph Parameters: The Case of Partition Functions.
Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

Hankel Matrices for Weighted Visibly Pushdown Automata.
Proceedings of the Language and Automata Theory and Applications, 2016

2015
Hankel Matrices for Weighted Visibly Pushdown Automata.
CoRR, 2015

Efficient computation of generalized Ising polynomials on graphs with fixed clique-width.
CoRR, 2015

Efficient Computation of Generalized Ising Polynomials on Graphs with Fixed Clique-Width.
Proceedings of the Topics in Theoretical Computer Science, 2015

Hankel Matrices: From Words to Graphs (Extended Abstract).
Proceedings of the Language and Automata Theory and Applications, 2015

Logics of Finite Hankel Rank.
Proceedings of the Fields of Logic and Computation II, 2015

2014
A representation theorem for (q-)holonomic sequences.
J. Comput. Syst. Sci., 2014

On the location of roots of graph polynomials.
Eur. J. Comb., 2014

Recurrence relations for graph polynomials on bi-iterative families of graphs.
Eur. J. Comb., 2014

Connection Matrices and the Definability of Graph Parameters.
Logical Methods in Computer Science, 2014

2013
On the Location of Roots of Graph Polynomials.
Electronic Notes in Discrete Mathematics, 2013

Weighted Automata and Monadic Second Order Logic.
Proceedings of the Proceedings Fourth International Symposium on Games, 2013

2012
Graph Polynomials: From Recursive Definitions to Subset Expansion Formulas.
J. Log. Comput., 2012

Foreword.
Fundam. Inform., 2012

A Representation Theorem for Holonomic Sequences Based on Counting Lattice Paths.
Fundam. Inform., 2012

Fifty years of the spectrum problem: survey and new results.
Bulletin of Symbolic Logic, 2012

A Computational Framework for the Study of Partition Functions and Graph Polynomials.
Proceedings of the 14th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, 2012

Definability and Complexity of Graph Parameters (Invited Talk).
Proceedings of the Computer Science Logic (CSL'12), 2012

Connection Matrices and the Definability of Graph Parameters.
Proceedings of the Computer Science Logic (CSL'12), 2012

BCNF via Attribute Splitting.
Proceedings of the Conceptual Modelling and Its Theoretical Foundations, 2012

2011
The Universal Edge Elimination Polynomial and the Dichromatic Polynomial.
Electronic Notes in Discrete Mathematics, 2011

The enumeration of vertex induced subgraphs with respect to the number of components.
Eur. J. Comb., 2011

Model Theory in Computer Science: My Own Recurrent Themes.
Proceedings of the Computer Science Logic, 2011

2010
Complexity of the Bollobás-Riordan Polynomial. Exceptional Points and Uniform Reductions.
Theory Comput. Syst., 2010

An extension of the bivariate chromatic polynomial.
Eur. J. Comb., 2010

Application of Logic to Integer Sequences: A Survey.
Proceedings of the Logic, 2010

The Ackermann Award 2010.
Proceedings of the Computer Science Logic, 24th International Workshop, 2010

Definability of Combinatorial Functions and Their Linear Recurrence Relations.
Proceedings of the Fields of Logic and Computation, 2010

2009
A Graph Polynomial Arising from Community Structure (Extended Abstract).
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2009

Connection Matrices for MSOL-Definable Structural Invariants.
Proceedings of the Logic and Its Applications, Third Indian Conference, 2009

The Ackermann Award 2009.
Proceedings of the Computer Science Logic, 23rd international Workshop, 2009

2008
From a Zoo to a Zoology: Towards a General Theory of Graph Polynomials.
Theory Comput. Syst., 2008

Notions of Sameness by Default and their Application to Anaphora, Vagueness, and Uncertain Reasoning.
Journal of Logic, Language and Information, 2008

Counting truth assignments of formulas of bounded tree-width or clique-width.
Discrete Applied Mathematics, 2008

Graph Polynomials: From Recursive Definitions To Subset Expansion Formulas
CoRR, 2008

From Hilbert's program to a logic tool box.
Ann. Math. Artif. Intell., 2008

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

A Most General Edge Elimination Polynomial.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2008

From Hilbert's Program to a Logic Toolbox.
Proceedings of the International Symposium on Artificial Intelligence and Mathematics, 2008

Complexity of the Bollobás-Riordan Polynomial.
Proceedings of the Computer Science, 2008

The Ackermann Award 2008.
Proceedings of the Computer Science Logic, 22nd International Workshop, 2008

On Counting Generalized Colorings.
Proceedings of the Computer Science Logic, 22nd International Workshop, 2008

Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants.
Proceedings of the Logic and Theory of Algorithms, 2008

Linear Recurrence Relations for Graph Polynomials.
Proceedings of the Pillars of Computer Science, 2008

2007
From Hilbert's Program to a Logic Toolbox.
Proceedings of the Logic for Programming, 2007

The Ackermann Award 2007.
Proceedings of the Computer Science Logic, 21st International Workshop, 2007

2006
Computing Graph Polynomials on Graphs of Bounded Clique-Width.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2006

The Ackermann Award 2006.
Proceedings of the Computer Science Logic, 20th International Workshop, 2006

From a Zoo to a Zoology: Descriptive Complexity for Graph Polynomials.
Proceedings of the Logical Approaches to Computational Barriers, 2006

2005
Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width.
Discrete Applied Mathematics, 2005

Clemens Lautemann: 1951-2005 An Obituary.
Proceedings of the Computer Science Logic, 19th International Workshop, 2005

The Ackermann Award 2005.
Proceedings of the Computer Science Logic, 19th International Workshop, 2005

Indistinguishability by Default.
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.
J. Symb. Log., 2004

Algorithmic uses of the Feferman-Vaught Theorem.
Ann. Pure Appl. Logic, 2004

2003
Tree-width and the monadic quantifier hierarchy.
Theor. Comput. Sci., 2003

The parametrized complexity of knot polynomials.
J. Comput. Syst. Sci., 2003

NCE Graph Grammars and Clique-Width.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2003

The Specker-Blatter Theorem Revisited.
Proceedings of the Computing and Combinatorics, 9th Annual International Conference, 2003

2002
Fusion in Relational Structures and the Verification of Monadic Second-Order Properties.
Mathematical Structures in Computer Science, 2002

2001
On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic.
Discrete Applied Mathematics, 2001

Colored Tutte polynomials and Kaufman brackets for graphs of bounded tree width.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

2000
Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width.
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.
Proceedings of the Computer Science Logic, 2000

1999
On the Clique-Width of Graphs with Few P4's.
Int. J. Found. Comput. Sci., 1999

1998
Extensions for Open Default Theories via the Domain Closure Assumption.
J. Log. Comput., 1998

Dependency Preserving Refinements and the Fundamental Problem of Database Design.
Data Knowl. Eng., 1998

Erratum to "Arity and Alternation in Second-Order Logic".
Ann. Pure Appl. Logic, 1998

Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1998

Invariant Definability and P/poly.
Proceedings of the Computer Science Logic, 12th International Workshop, 1998

1997
Finitary Sketches.
J. Symb. Log., 1997

Restrictions of Minimum Spanner Problems.
Inf. Comput., 1997

The Fundamental Problem of Database Design.
Proceedings of the SOFSEM '97: Theory and Practice of Informatics, 1997

Invariant Definability (Extended Abstract).
Proceedings of the Computational Logic and Proof Theory, 5th Kurt Gödel Colloquium, 1997

1996
Arity and Alternation in Second-Order Logic.
Ann. Pure Appl. Logic, 1996

Extensions for Open Default Theories via the Domain Closure Assumption.
Proceedings of the Logics in Artificial Intelligence, European Workshop, 1996

Translation Schemes and the Fundamental Problem of Database Design.
Proceedings of the Conceptual Modeling, 1996

1995
On Average Case Complexity of SAT for Symmetric Distribution.
J. Log. Comput., 1995

Incremental Model Checking for Decomposable Structures (Extended Abstract).
Proceedings of the Mathematical Foundations of Computer Science 1995, 1995

1994
Capturing Complexity Classes with Lindström Quantifiers.
Proceedings of the Mathematical Foundations of Computer Science 1994, 1994

Arity vs. Alternation in Second Order Logic.
Proceedings of the Logical Foundations of Computer Science, Third International Symposium, 1994

Logics Capturing Relativized Complexity Classes Uniformly.
Proceedings of the Logical and Computational Complexity. Selected Papers. Logic and Computational Complexity, 1994

1993
Oracles and Quantifiers.
Proceedings of the Computer Science Logic, 7th Workshop, 1993

1992
Query Languages for Hierarchic Databases
Inf. Comput., November, 1992

The Expressive Power of Side Effects in Prolog.
J. Log. Program., 1992

Formal Interactive Menu Design.
Interacting with Computers, 1992

The Ehrenfeucht-Fraisse Games for Transitive Closure.
Proceedings of the Logical Foundations of Computer Science, 1992

1991
Decidability of Finite Probablistic Propositional Dynamic Logics
Inf. Comput., October, 1991

The Expressive Power of Transitive Closue and 2-way Multihead Automata.
Proceedings of the Computer Science Logic, 5th Workshop, 1991

1990
Identifying Extended Entity-Relationship Object Structures in Relational Schemas.
IEEE Trans. Software Eng., 1990

1989
Weak Second Order Characterizations of Various Program Verification Systems.
Theor. Comput. Sci., 1989

1988
On the existence of polynomial time algorithms for interpolation problems in propositional logic.
Notre Dame Journal of Formal Logic, 1988

Incremental Restructuring of Relational Schemas.
Proceedings of the Fourth International Conference on Data Engineering, 1988

1987
Unification as a Complexity Measure for Logic Programming.
J. Log. Program., 1987

Why Horn Formulas Matter in Computer Science: Initial Structures and Generic Examples.
J. Comput. Syst. Sci., 1987

Incremental Reorganization of Relational Databases.
Proceedings of the VLDB'87, 1987

1986
On the Expressive Power of Data Dependencies.
Acta Inf., 1986

On the Equivalence of Weak Second Order and Nonstandard Time Semantics For Various Program Verification Systems
Proceedings of the Symposium on Logic in Computer Science (LICS '86), 1986

Musician - A Music Processing and Synthesis System.
Proceedings of the 1986 International Computer Music Conference, 1986

Entity-Relationship Consistency for Relational Schemas.
Proceedings of the ICDT'86, 1986

The Choice of Programming Primitives for SETL-Like Programming Languages.
Proceedings of the ESOP 86, 1986

Computable Directory Queries.
Proceedings of the CAAP '86, 1986

1985
Propositional Dynamic Logic with Local Assignments.
Theor. Comput. Sci., 1985

Vopenka's Principle and Compact Logics.
J. Symb. Log., 1985

A Proof Rule for Fair Termination of Guarded Commands
Information and Control, 1985

Why Horn Formulas Matter in Computer Science: Initial Structures and Generic Examples (Extended Abstract).
Proceedings of the Mathematical Foundations of Software Development, 1985

1984
Characterizing Specification Languages which Admit Initial Semantics.
Theor. Comput. Sci., 1984

1983
Positive results in abstract model theory: a theory of compact logics.
Ann. Pure Appl. Logic, 1983

An axiomatic approach to semantics of specification languages.
Proceedings of the Theoretical Computer Science, 1983

Characterizing Specification Languages Which Admit Initial Semantics.
Proceedings of the CAAP'83, 1983

1981
The theorems of beth and Craig in abstract model theory II. Compact logics.
Arch. Math. Log., 1981

Topological model theory with an interior operator: Consistency properties and back - and forth arguments.
Arch. Math. Log., 1981

Embedded Implicational Dependencies and their Inference Problem
Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981

Errata: Measuring the Expressive Power of Dynamic Logics: An Application of Abstract Model Theory.
Proceedings of the Automata, 1981

Characterizing Data Base Dependencies.
Proceedings of the Automata, 1981

1980
Embedded Implicational Dependencies and their Inference Problem.
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.
Proceedings of the Automata, 1980

1977
Completeness Theorems For Modal Model Theory With the Montague-Chang Semantics I.
Math. Log. Q., 1977

Some model theory for monotone quantifiers.
Arch. Math. Log., 1977


  Loading...