Johann A. Makowsky

151 papers A* 8A 3B 28C 7Misc 6Journal 76Unranked 21
YearRankTypeTitle / Venue / Authors
2025 J jnl
Courcelle's Theorem Without Logic.
CoRR
Yuval Filmus, Johann A. Makowsky
2025 — conf
The Specker-Blatter Theorem: An Application of Logic to Combinatorial Counting.
ICLA
Johann A. Makowsky
2024 B conf
Extensions and Limits of the Specker-Blatter Theorem.
CSL
Eldar Fischer, Johann A. Makowsky
2024 J jnl
Extensions and Limits of the Specker-Blatter Theorem.
J. Symb. Log.
Eldar Fischer, Johann A. Makowsky
2023 J jnl
Almost unimodal and real-rooted graph polynomials.
Eur. J. Comb.
Johann A. Makowsky, Vsevolod Rakita
2022 J jnl
On the Tutte and Matching Polynomials for Complete Graphs.
Fundam. Informaticae
Tomer Kotek, Johann A. Makowsky
2021 — conf
Some Thoughts on Computational Models: From Massive Human Computing to Abstract State Machines, and Beyond.
Logic, Computation and Rigorous Methods
Johann A. Makowsky
2020 J jnl
Harary polynomials.
CoRR
Orli Herscovici, Johann A. Makowsky, Vsevolod Rakita
2020 — conf
To Yuri at 80 and More than 40 Years of Friendship.
Fields of Logic and Computation III
Johann A. Makowsky
2019 J jnl
A logician's view of graph polynomials.
Ann. Pure Appl. Log.
Johann A. Makowsky, Elena V. Ravve, Tomer Kotek
2019 J jnl
Can one design a geometry engine? - On the (un)decidability of certain affine Euclidean geometries.
Ann. Math. Artif. Intell.
Johann A. Makowsky
2019 J jnl
On
Australas. J Comb.
Johann A. Makowsky, R. X. Zhang
2019 J jnl
On Weakly Distinguishing Graph Polynomials.
Discret. Math. Theor. Comput. Sci.
Johann A. Makowsky, Vsevolod Rakita
2019 J jnl
The exact complexity of the Tutte polynomial.
CoRR
Tomer Kotek, Johann A. Makowsky
2018 J jnl
On sequences of polynomials arising from graph invariants.
Eur. J. Comb.
Tomer Kotek, Johann A. Makowsky, Elena V. Ravve
2018 J jnl
On the complexity of generalized chromatic polynomials.
Adv. Appl. Math.
Andrew J. Goodall, Miki Hermann, Tomer Kotek, Johann A. Makowsky, Steven D. Noble
2018 C conf
The Undecidability of Orthogonal and Origami Geometries.
WoLLIC
Johann A. Makowsky
2017 J jnl
Can one design a geometry engine? On the (un)decidability of affine Euclidean geometries.
CoRR
Johann A. Makowsky
2017 J jnl
Keeping logic in the trivium of computer science: a teaching perspective.
Formal Methods Syst. Des.
Johann A. Makowsky, Anna Zamansky
2017 J jnl
On the complexity of generalized chromatic polynomials.
CoRR
Andrew J. Goodall, Miki Hermann, Tomer Kotek, Johann A. Makowsky, Steven D. Noble
2016 J jnl
Graph Polynomials: Towards a Comparative Theory (Dagstuhl Seminar 16241).
Dagstuhl Reports
Joanna A. Ellis-Monaghan, Andrew J. Goodall, Johann A. Makowsky, Iain Moffatt
2016 C conf
Hankel Matrices for Weighted Visibly Pushdown Automata.
LATA
Nadia Labai, Johann A. Makowsky
2016 B conf
On the Exact Learnability of Graph Parameters: The Case of Partition Functions.
MFCS
Nadia Labai, Johann A. Makowsky
2016 J jnl
On the exact learnability of graph parameters: The case of partition functions.
CoRR
Nadia Labai, Johann A. Makowsky
2016 C conf
Semantic Equivalence of Graph Polynomials Definable in Second Order Logic.
WoLLIC
Johann A. Makowsky, Elena V. Ravve
2015 — conf
Efficient Computation of Generalized Ising Polynomials on Graphs with Fixed Clique-Width.
TTCS
Tomer Kotek, Johann A. Makowsky
2015 J jnl
Efficient computation of generalized Ising polynomials on graphs with fixed clique-width.
CoRR
Tomer Kotek, Johann A. Makowsky
2015 J jnl
Hankel Matrices for Weighted Visibly Pushdown Automata.
CoRR
Nadia Labai, Johann A. Makowsky
2015 C conf
Hankel Matrices: From Words to Graphs (Extended Abstract).
LATA
Johann A. Makowsky, Nadia Labai
2015 — conf
Logics of Finite Hankel Rank.
Fields of Logic and Computation II
Nadia Labai, Johann A. Makowsky
2015 J jnl
Teaching Logic for Computer Science: Are We Teaching the Wrong Narrative?
CoRR
Johann A. Makowsky
2014 J jnl
A representation theorem for (q-)holonomic sequences.
J. Comput. Syst. Sci.
Tomer Kotek, Johann A. Makowsky
2014 J jnl
Connection Matrices and the Definability of Graph Parameters.
Log. Methods Comput. Sci.
Tomer Kotek, Johann A. Makowsky
2014 J jnl
On the location of roots of graph polynomials.
Eur. J. Comb.
Johann A. Makowsky, Elena V. Ravve, N. K. Blanchard
2014 J jnl
Recurrence relations for graph polynomials on bi-iterative families of graphs.
Eur. J. Comb.
Tomer Kotek, Johann A. Makowsky
2013 J jnl
On the Location of Roots of Graph Polynomials.
Electron. Notes Discret. Math.
Johann A. Makowsky, Elena V. Ravve
2013 — conf
Weighted Automata and Monadic Second Order Logic.
GandALF
Nadia Labai, Johann A. Makowsky
2012 Misc conf
A Computational Framework for the Study of Partition Functions and Graph Polynomials.
SYNASC
Tomer Kotek, Johann A. Makowsky, Elena V. Ravve
2012 J jnl
A Representation Theorem for Holonomic Sequences Based on Counting Lattice Paths.
Fundam. Informaticae
Tomer Kotek, Johann A. Makowsky
2012 — conf
BCNF via Attribute Splitting.
Conceptual Modelling and Its Theoretical Foundations
Johann A. Makowsky, Elena V. Ravve
2012 B conf
Connection Matrices and the Definability of Graph Parameters.
CSL
Tomer Kotek, Johann A. Makowsky
2012 B conf
Definability and Complexity of Graph Parameters (Invited Talk).
CSL
Johann A. Makowsky
2012 J jnl
Fifty years of the spectrum problem: survey and new results.
Bull. Symb. Log.
Arnaud Durand, Neil D. Jones, Johann A. Makowsky, Malika More
2012 J jnl
Foreword.
Fundam. Informaticae
Sri Gopal Mohanty, Simone Rinaldi, Johann A. Makowsky
2012 J jnl
Graph Polynomials: From Recursive Definitions to Subset Expansion Formulas.
J. Log. Comput.
Benny Godlin, Emilia Katz, Johann A. Makowsky
2011 — ed.
Model Theoretic Methods in Finite Combinatorics - AMS-ASL Joint Special Session, Washington, DC, USA, January 5-8, 2009.
AMS-ASL Joint Special Session
Martin Grohe, Johann A. Makowsky
2011 B conf
Model Theory in Computer Science: My Own Recurrent Themes.
CSL
Johann A. Makowsky
2011 J jnl
The Universal Edge Elimination Polynomial and the Dichromatic Polynomial.
Electron. Notes Discret. Math.
Ilya Averbouch, Tomer Kotek, Johann A. Makowsky, Elena V. Ravve
2011 J jnl
The enumeration of vertex induced subgraphs with respect to the number of components.
Eur. J. Comb.
Peter Tittmann, Ilya Averbouch, Johann A. Makowsky
2010 J jnl
An extension of the bivariate chromatic polynomial.
Eur. J. Comb.
Ilya Averbouch, Benny Godlin, Johann A. Makowsky
2010 C conf
Application of Logic to Integer Sequences: A Survey.
WoLLIC
Johann A. Makowsky
2010 J jnl
Complexity of the Bollobás-Riordan Polynomial. Exceptional Points and Uniform Reductions.
Theory Comput. Syst.
Markus Bläser, Holger Dell, Johann A. Makowsky
2010 — conf
Definability of Combinatorial Functions and Their Linear Recurrence Relations.
Fields of Logic and Computation
Tomer Kotek, Johann A. Makowsky
2010 B conf
The Ackermann Award 2010.
CSL
Johann A. Makowsky, Damian Niwinski
2009 B conf
A Graph Polynomial Arising from Community Structure (Extended Abstract).
WG
Ilya Averbouch, Johann A. Makowsky, Peter Tittmann
2009 — conf
Application of logic to combinatorial sequences and their recurrence relations.
AMS-ASL Joint Special Session
Eldar Fischer, Tomer Kotek, Johann A. Makowsky
2009 — conf
Connection Matrices for MSOL-Definable Structural Invariants.
ICLA
Johann A. Makowsky
2009 — conf
On Counting Generalized Colorings.
AMS-ASL Joint Special Session
Tomer Kotek, Johann A. Makowsky, Boris Zilber
2009 B conf
The Ackermann Award 2009.
CSL
Johann A. Makowsky, Alexander A. Razborov
2008 B conf
A Most General Edge Elimination Polynomial.
WG
Ilya Averbouch, Benny Godlin, Johann A. Makowsky
2008 Misc conf
Complexity of the Bollobás-Riordan Polynomial.
CSR
Markus Bläser, Holger Dell, Johann A. Makowsky
2008 J jnl
Counting truth assignments of formulas of bounded tree-width or clique-width.
Discret. Appl. Math.
Eldar Fischer, Johann A. Makowsky, Elena V. Ravve
2008 B conf
Evaluations of Graph Polynomials.
WG
Benny Godlin, Tomer Kotek, Johann A. Makowsky
2008 Misc conf
From Hilbert's Program to a Logic Toolbox.
ISAIM
Johann A. Makowsky
2008 J jnl
From Hilbert's program to a logic tool box.
Ann. Math. Artif. Intell.
Johann A. Makowsky
2008 J jnl
From a Zoo to a Zoology: Towards a General Theory of Graph Polynomials.
Theory Comput. Syst.
Johann A. Makowsky
2008 J jnl
Graph Polynomials: From Recursive Definitions To Subset Expansion Formulas
CoRR
Benny Godlin, Emilia Katz, Johann A. Makowsky
2008 — conf
Linear Recurrence Relations for Graph Polynomials.
Pillars of Computer Science
Eldar Fischer, Johann A. Makowsky
2008 J jnl
Notions of Sameness by Default and their Application to Anaphora, Vagueness, and Uncertain Reasoning.
J. Log. Lang. Inf.
Ariel Cohen, Michael Kaminski, Johann A. Makowsky
2008 B conf
On Counting Generalized Colorings.
CSL
Tomer Kotek, Johann A. Makowsky, Boris Zilber
2008 B conf
The Ackermann Award 2008.
CSL
Johann A. Makowsky, Damian Niwinski
2008 C conf
Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants.
CiE
Johann A. Makowsky
2007 B conf
From Hilbert's Program to a Logic Toolbox.
LPAR
Johann A. Makowsky
2007 B conf
The Ackermann Award 2007.
CSL
Martin Grohe, Martin Hyland, Johann A. Makowsky, Damian Niwinski
2006 B conf
Computing Graph Polynomials on Graphs of Bounded Clique-Width.
WG
Johann A. Makowsky, Udi Rotics, Ilya Averbouch, Benny Godlin
2006 C conf
From a Zoo to a Zoology: Descriptive Complexity for Graph Polynomials.
CiE
Johann A. Makowsky
2006 B conf
The Ackermann Award 2006.
CSL
Samson Abramsky, Erich Grädel, Johann A. Makowsky
2005 B conf
Clemens Lautemann: 1951-2005
CSL
Johann A. Makowsky
2005 J jnl
Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width.
Discret. Appl. Math.
Johann A. Makowsky
2005 — conf
Indistinguishability by Default.
We Will Show Them! (1)
Ariel Cohen, Michael Kaminski, Johann A. Makowsky
2004 J jnl
Algorithmic uses of the Feferman-Vaught Theorem.
Ann. Pure Appl. Log.
Johann A. Makowsky
2004 J jnl
On spectra of sentences of monadic second order logic with counting.
J. Symb. Log.
Eldar Fischer, Johann A. Makowsky
2004 J jnl
On the algebraic complexity of some families of coloured Tutte polynomials.
Adv. Appl. Math.
Martin Lotz, Johann A. Makowsky
2003 B ed.
Computer Science Logic, 17th International Workshop, CSL 2003, 12th Annual Conference of the EACSL, and 8th Kurt Gödel Colloquium, KGC 2003, Vienna, Austria, August 25-30, 2003, Proceedings
CSL
Matthias Baaz, Johann A. Makowsky
2003 J jnl
Farrell polynomials on graphs of bounded tree width.
Adv. Appl. Math.
Johann A. Makowsky, Julian Mariño
2003 B conf
NCE Graph Grammars and Clique-Width.
WG
Alexander Glikson, Johann A. Makowsky
2003 Misc conf
The Specker-Blatter Theorem Revisited.
COCOON
Eldar Fischer, Johann A. Makowsky
2003 J jnl
The parametrized complexity of knot polynomials.
J. Comput. Syst. Sci.
Johann A. Makowsky, Julian Mariño
2003 J jnl
Tree-width and the monadic quantifier hierarchy.
Theor. Comput. Sci.
Johann A. Makowsky, Julian Mariño
2002 J jnl
Fusion in Relational Structures and the Verification of Monadic Second-Order Properties.
Math. Struct. Comput. Sci.
Bruno Courcelle, Johann A. Makowsky
2001 A* conf
Colored Tutte polynomials and Kaufman brackets for graphs of bounded tree width.
SODA
Johann A. Makowsky
2001 J jnl
On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic.
Discret. Appl. Math.
Bruno Courcelle, Johann A. Makowsky, Udi Rotics
2000 J jnl
Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width.
Theory Comput. Syst.
Bruno Courcelle, Johann A. Makowsky, Udi Rotics
2000 B conf
On the Complexity of Combinatorial and Metafinite Generating Functions of Graph Properties in the Computational Model of Blum, Shub and Smale.
CSL
Johann A. Makowsky, Klaus Meer
1999 J jnl
On the Clique-Width of Graphs with Few P
Int. J. Found. Comput. Sci.
Johann A. Makowsky, Udi Rotics
1998 J jnl
Dependency Preserving Refinements and the Fundamental Problem of Database Design.
Data Knowl. Eng.
Johann A. Makowsky, Elena V. Ravve
1998 J jnl
Erratum to "Arity and Alternation in Second-Order Logic".
Ann. Pure Appl. Log.
Johann A. Makowsky, Y. B. Pnueli
1998 J jnl
Extensions for Open Default Theories via the Domain Closure Assumption.
J. Log. Comput.
Michael Kaminski, Johann A. Makowsky, Michael L. Tiomkin
1998 B conf
Invariant Definability and P/
CSL
Johann A. Makowsky
1998 B conf
Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width.
WG
Bruno Courcelle, Johann A. Makowsky, Udi Rotics
1998 — ed.
Proceedings of the Annual European Summer Meeting of the Association of Symbolic Logic, Logic Colloquium 1995, Haifa, Israel, August 9-18, 1995
Logic Colloquium
Johann A. Makowsky, Elena V. Ravve
1997 J jnl
Finitary Sketches.
J. Symb. Log.
Jirí Adámek, Peter T. Johnstone, Johann A. Makowsky, Jirí Rosický
1997 — conf
Invariant Definability (Extended Abstract).
Kurt Gödel Colloquium
Johann A. Makowsky
1997 J jnl
Restrictions of Minimum Spanner Problems.
Inf. Comput.
G. Venkatesan, Udi Rotics, M. S. Madanlal, Johann A. Makowsky, C. Pandu Rangan
1997 B conf
The Fundamental Problem of Database Design.
SOFSEM
Johann A. Makowsky, Elena V. Ravve
1996 J jnl
Arity and Alternation in Second-Order Logic.
Ann. Pure Appl. Log.
Johann A. Makowsky, Y. B. Pnueli
1996 B conf
Extensions for Open Default Theories via the Domain Closure Assumption.
JELIA
Michael Kaminski, Johann A. Makowsky, Michael L. Tiomkin
1996 A conf
Translation Schemes and the Fundamental Problem of Database Design.
ER
Johann A. Makowsky, Elena V. Ravve
1995 B conf
Incremental Model Checking for Decomposable Structures (Extended Abstract).
MFCS
Johann A. Makowsky, Elena V. Ravve
1995 J jnl
On Average Case Complexity of SAT for Symmetric Distribution.
J. Log. Comput.
Johann A. Makowsky, Abraham Sharell
1994 Misc conf
Arity vs. Alternation in Second Order Logic.
LFCS
Johann A. Makowsky, Y. B. Pnueli
1994 B conf
Capturing Complexity Classes with Lindström Quantifiers.
MFCS
Johann A. Makowsky
1994 — conf
Logics Capturing Relativized Complexity Classes Uniformly.
LCC
Johann A. Makowsky, Y. B. Pnueli
1993 J jnl
Book Review: Predicate Transformer Semantics. By Ernest G. Manes. (Cambridge University Press, 1992, 233pp. ISBN 0-521-42036-9. $39.95).
SIGACT News
Johann A. Makowsky
1993 B conf
Oracles and Quantifiers.
CSL
Johann A. Makowsky, Y. B. Pnueli
1992 J jnl
Formal Interactive Menu Design.
Interact. Comput.
Jacob P. Ukelson, Johann A. Makowsky
1992 J jnl
Query Languages for Hierarchic Databases
Inf. Comput.
Elias Dahlhaus, Johann A. Makowsky
1992 Misc conf
The Ehrenfeucht-Fraisse Games for Transitive Closure.
LFCS
A. Calò, Johann A. Makowsky
1992 J jnl
The Expressive Power of Side Effects in Prolog.
J. Log. Program.
Johann A. Makowsky, J.-C. Gregoire, Shmuel Sagiv
1991 J jnl
Decidability of Finite Probablistic Propositional Dynamic Logics
Inf. Comput.
Michael L. Tiomkin, Johann A. Makowsky
1991 B conf
The Expressive Power of Transitive Closue and 2-way Multihead Automata.
CSL
Yaniv Bargury, Johann A. Makowsky
1990 J jnl
Identifying Extended Entity-Relationship Object Structures in Relational Schemas.
IEEE Trans. Software Eng.
Victor M. Markowitz, Johann A. Makowsky
1989 J jnl
Weak Second Order Characterizations of Various Program Verification Systems.
Theor. Comput. Sci.
Johann A. Makowsky, Ildikó Sain
1988 A* conf
Incremental Restructuring of Relational Schemas.
ICDE
Victor M. Markowitz, Johann A. Makowsky
1988 J jnl
On the existence of polynomial time algorithms for interpolation problems in propositional logic.
Notre Dame J. Formal Log.
Elias Dahlhaus, Amos Israeli, Johann A. Makowsky
1987 A* conf
Incremental Reorganization of Relational Databases.
VLDB
Victor M. Markowitz, Johann A. Makowsky
1987 J jnl
Unification as a Complexity Measure for Logic Programming.
J. Log. Program.
Alon Itai, Johann A. Makowsky
1987 J jnl
Why Horn Formulas Matter in Computer Science: Initial Structures and Generic Examples.
J. Comput. Syst. Sci.
Johann A. Makowsky
1986 — conf
Computable Directory Queries.
CAAP
Elias Dahlhaus, Johann A. Makowsky
1986 A conf
Entity-Relationship Consistency for Relational Schemas.
ICDT
Johann A. Makowsky, Victor M. Markowitz, Nimrod Rotics
1986 — conf
Musician - A Music Processing and Synthesis System.
ICMC
A. Ban, Johann A. Makowsky
1986 A* conf
On the Equivalence of Weak Second Order and Nonstandard Time Semantics For Various Program Verification Systems
LICS
Johann A. Makowsky, Ildikó Sain
1986 J jnl
On the Expressive Power of Data Dependencies.
Acta Informatica
Johann A. Makowsky, Moshe Y. Vardi
1986 A conf
The Choice of Programming Primitives for SETL-Like Programming Languages.
ESOP
Elias Dahlhaus, Johann A. Makowsky
1985 J jnl
A Proof Rule for Fair Termination of Guarded Commands
Inf. Control.
Orna Grumberg, Nissim Francez, Johann A. Makowsky, Willem P. de Roever
1985 J jnl
Propositional Dynamic Logic with Local Assignments.
Theor. Comput. Sci.
Michael L. Tiomkin, Johann A. Makowsky
1985 J jnl
Vopenka's Principle and Compact Logics.
J. Symb. Log.
Johann A. Makowsky
1985 — conf
Why Horn Formulas Matter in Computer Science: Initial Structures and Generic Examples (Extended Abstract).
TAPSOFT, Vol.1
Johann A. Makowsky
1984 J jnl
Characterizing Specification Languages which Admit Initial Semantics.
Theor. Comput. Sci.
Bernd Mahr, Johann A. Makowsky
1983 — conf
An axiomatic approach to semantics of specification languages.
Theoretical Computer Science
Johann A. Makowsky, Bernd Mahr
1983 — conf
Characterizing Specification Languages Which Admit Initial Semantics.
CAAP
Bernd Mahr, Johann A. Makowsky
1983 J jnl
Positive results in abstract model theory: a theory of compact logics.
Ann. Pure Appl. Log.
Johann A. Makowsky, Saharon Shelah
1981 A* conf
Characterizing Data Base Dependencies.
ICALP
Johann A. Makowsky
1981 A* conf
Embedded Implicational Dependencies and their Inference Problem
STOC
Ashok K. Chandra, Harry R. Lewis, Johann A. Makowsky
1981 A* conf
Errata: Measuring the Expressive Power of Dynamic Logics: An Application of Abstract Model Theory.
ICALP
Johann A. Makowsky
1981 J jnl
The theorems of beth and Craig in abstract model theory II. Compact logics.
Arch. Math. Log.
Johann A. Makowsky, Johann Shelah
1981 J jnl
Topological model theory with an interior operator: Consistency properties and back - and forth arguments.
Arch. Math. Log.
Johann A. Makowsky, Martin Ziegler
1980 — conf
Embedded Implicational Dependencies and their Inference Problem.
XP1 Workshop on Database Theory
Ashok K. Chandra, Harry R. Lewis, Johann A. Makowsky
1980 A* conf
Measuring the Expressive Power of Dynamic Logics: An Application of Abstract Model Theory.
ICALP
Johann A. Makowsky
1977 J jnl
Completeness Theorems For Modal Model Theory With the Montague-Chang Semantics I.
Math. Log. Q.
Johann A. Makowsky, Annalisa Marcja
1977 J jnl
Some model theory for monotone quantifiers.
Arch. Math. Log.
Johann A. Makowsky, Sauro Tulipani